$\text{Estudio Empírico del Problema de Alquiler de Canoas}$¶
Índice General:¶
- Introducción
- Enunciado del Problema
- 2.1. Ejemplo de Instancia
- 2.2. Justificación de los 3 Algoritmos
- Metodología y Diseño del Experimento
- 3.1. Objetivos de Investigación
- 3.2. Hipótesis
- 3.3. Variables
- 3.4. Tamaño de Instancias
- 3.5. Plan de Ejecución
- 3.6. Generación de Instancias
- 3.7. Herramientas y Librerías
- Implementación en Python
- 4.1. Funciones para Generar Instancias
- 4.2. Algoritmos a Comparar
- 4.3. Pruebas Unitarias
- 4.4. Función Principal de Experimentos
- Análisis Estadístico y Validación de Hipótesis
- 5.1. Estadística Descriptiva (
psutil) - 5.2. Contraste de Hipótesis
- 5.2.1. ANOVA
- 5.2.2. Pruebas Post-hoc
- 5.2.3. Prueba t-Test
- 5.3. Estadística Descriptiva (
tracemalloc) - 5.4. Contraste de Hipótesis
- 5.4.1. ANOVA
- 5.4.2. Pruebas Post-hoc
- 5.4.3. Prueba t-Test
- Regresiones y Técnicas de Machine Learning
- Discusión de Resultados
- Conclusiones
- Reproducibilidad
- Ética de la Investigación
- Referencias Bibliográficas
1. Introducción¶
Este proyecto analiza empíricamente el Problema de Alquiler de Canoas, que consiste en alquilar canoas en distintos puertos a lo largo de un río y devolverlas río abajo, minimizando el costo total de viaje. Existen costos directos entre puertos que pueden no ser aditivos, lo cual motiva comparaciones entre tres enfoques algorítmicos fundamentales:
- Fuerza Bruta Recursiva (exploración exhaustiva sin optimización).
- Recursión con Memoización (optimización top-down con almacenamiento de subproblemas).
- Programación Dinámica (solución iterativa bottom-up).
Para evaluar el rendimiento de estas soluciones se diseñará un experimento masivo con distintos tamaños de instancias (XS, S, M, L, XL) y varias réplicas, midiendo tiempo de ejecución y uso de memoria. Además, se contempla la ejecución en múltiples lenguajes de programación con posterior unificación de los datos, permitiendo así un análisis estadístico extenso, validación de hipótesis, y eventualmente modelado predictivo (regresiones, machine learning) del rendimiento.
2. Enunciado del Problema¶
- Número de Puertos ($n$): Se enumeran de 1 a ($n$).
- Matriz de Costos ($\text{costo}[i][j])$: Representa el costo de alquilar una canoa en el puerto ($i$) y devolverla en el puerto ($j$) (con $(i < j)$).
- Observación: Es posible que viajar directamente $(i \to j)$ sea más costoso que fraccionar el viaje en varios tramos intermedios, por lo que la solución óptima podría involucrar paradas.
- Objetivo: Minimizar el costo total desde un puerto inicial (usualmente 1) hasta un puerto final (usualmente ($n$)).
Nos interesa comparar distintos métodos para resolver el problema, considerando tiempo y memoria.
2.1 Ejemplo de Instancia¶
Supongamos que hay 5 puertos a lo largo del río, numerados del 1 al 5. Se tiene la siguiente matriz de costos de alquiler de canoas entre los puertos:
| De / A | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 1 | 0 | 10 | 25 | 30 | 50 |
| 2 | - | 0 | 12 | 20 | 35 |
| 3 | - | - | 0 | 8 | 15 |
| 4 | - | - | - | 0 | 5 |
| 5 | - | - | - | - | 0 |
Donde el valor en la celda (i, j) representa el costo de alquilar una canoa desde el puerto i hasta el puerto j. Un guion - indica que no se puede viajar río arriba.
En este caso, aunque el costo de alquilar una canoa de 1 a 4 directamente es 30, podríamos notar que:
- Ir de 1 a 3 cuesta 25.
- Luego, tomar otra canoa de 3 a 4 cuesta 8. El costo total usando esta estrategia sería 25 + 8 = 33, que es mayor que el alquiler directo, por lo que no conviene.
Sin embargo, para viajar de 1 a 5, si se toma la ruta directa, el costo es 50, pero podemos evaluar otras opciones:
- Ir de 1 a 3 (25) y luego de 3 a 5 (15) da un total de 40, que es más barato que el alquiler directo de 1 a 5 (50).
- Ir de 1 a 2 (10), luego de 2 a 4 (20) y después de 4 a 5 (5) da un total de 10 + 20 + 5 = 35, que es aún más barato.
Así, el costo mínimo de 1 a 5 sería 35 usando la combinación óptima de alquileres.
2.2 Justificación de los 3 Algoritmos¶
Fuerza Bruta Recursiva
Complejidad Temporal: $O(2^n)$ (exponencial).
Complejidad Espacial: $O(n)$ (profundidad de la pila de recursión).
Propósito: Sirve como línea base para entender el comportamiento del problema sin optimizaciones. Su naturaleza recursiva explora todas las rutas posibles mediante un árbol de decisiones, lo que lo hace inviable para $n > 20$.
Recursión con Memoización
Complejidad Temporal: $O(n^2)$.
Complejidad Espacial: $O(n)$ (tabla de memoización $O(n)$ + pila de recursión $O(n)$).
Propósito: Demuestra cómo la memoización reduce drásticamente la complejidad al evitar recálculos. Es una optimización natural de la fuerza bruta recursiva.
Programación Dinámica (Bottom-Up)
Complejidad Temporal: $O(n^2)$.
Complejidad Espacial: $O(n)$ (arreglo unidimensional para almacenar costos mínimos).
Propósito: Representa la solución más eficiente en términos de memoria y tiempo constante, al eliminar la sobrecarga de la recursión.
3. Metodología y Diseño del Experimento¶
3.1 Objetivos de Investigación¶
Comparar los tiempos de ejecución y uso de memoria de tres enfoques algorítmicos para el Problema de Alquiler de Canoas:
- Fuerza Bruta Recursivo (equivalente a recursividad sin memoización).
- Recursivo con Memoización.
- Programación Dinámica (Bottom-Up).
Validar empíricamente las complejidades teóricas de estos métodos: exponencial $O(2^n)$ para el Fuerza Bruta Recursivo versus $O(n^2)$ para los métodos optimizados.
Probar estadísticamente si, para tamaños de instancia grandes, la Programación Dinámica y el Recursivo con Memoización superan significativamente a la Fuerza Bruta Recursivo.
Generar un dataset amplio (posiblemente con miles o decenas de miles de instancias) para un análisis avanzado (regresiones, machine learning).
Permitir la ejecución en C y Python, con posterior unificación de resultados.
3.2 Hipótesis¶
- (Hipótesis de Tiempo)
H0 (nula): No existe diferencia estadísticamente significativa en el tiempo de ejecución promedio de los tres algoritmos.
H1 (alternativa): La Programación Dinámica y el Recursivo con Memoización exhiben menor tiempo de ejecución promedio que la Fuerza Bruta Recursivo, especialmente cuando $n$ es mediano/grande.
- (Hipótesis de Memoria)
H0: No existe diferencia estadísticamente significativa en el uso de memoria entre el Recursivo con Memoización y la Programación Dinámica.
H1: El Recursivo con Memoización utiliza, en promedio, más memoria debido a la combinación de la pila de llamadas y la tabla de memoización.
3.3 Variables¶
Variables Independientes:
- Tamaño de instancia ( $ n $ ): Categorías XS, S, M, L, XL.
- Algoritmo: {Fuerza Bruta Recursivo, Recursivo con Memoización, PD Bottom-Up}.
- Tipo de instancia: {Aleatoria Uniforme, Aleatoria Estructurada}.
- Réplicas: Número de repeticiones por combinación.
- Lenguaje: Identificador del lenguaje de programación donde se ejecuta.
Variables Dependientes:
- Tiempo de ejecución (segundos, medido con
time.perf_counter()). - Uso de memoria (MB, medido con
memory_profiler). - Costo Mínimo (para verificar correctitud).
- Tiempo de ejecución (segundos, medido con
3.4 Tamaño de Instancias (XS, S, M, L, XL)¶
Propuesta:
- XS: $n \in \{4, 5, 7, 10, 14\}$
- S: $n \in \{15, 18, 20, 22, 24\}$
- M: $n \in \{25, 30, 35, 40, 45\}$
- L: $n \in \{50, 60, 70, 80, 90\}$
- XL: $n \in \{100, 120, 150, 200, 400\}$
Omitir fuerza bruta recursivo en escalas muy altas si su tiempo es excesivo por ejemplo $n \leq 15$
3.5 Plan de Ejecución Paso a Paso¶
- Crear un diccionario que asocia cada categoría (XS, S, M, L, XL) con sus valores de $n$.
- Para cada $n$ de cada categoría:
- Para cada tipo de instancia (Uniforme, Estructurada):
- Generar la matriz de costos, usando semillas (para reproducibilidad).
- Para cada algoritmo:
- Medir tiempo y memoria.
- Almacenar resultado en un
DataFramedepandascon columnas:language_id,category_size,n,tipo_instancia,algoritmo,replica_id,tiempo_ejecucion,memoria_max_mb,costo_minimoystatus.
- Para cada tipo de instancia (Uniforme, Estructurada):
- Repetir réplicas (p.ej. 50) para capturar variabilidad estadística.
- Guardar los datos en un CSV (o varios CSV) por lenguaje.
- Unir CSV de todas los lenguajes (2) en un único dataset para análisis conjunto.
3.6 Generación de Instancias¶
- Aleatoria Uniforme: $ \text{costo}[i][j] \sim \text{Uniform}(1,10) \quad (\text{enteros}) $
- Aleatoria Estructurada (pseudo-aditiva):
- Inicializar $\text{costo}[i][j]$ con valores en $[1,10]$.
- “Refinar” usando reglas aditivas:
\begin{equation} \begin{aligned} \text{costo}[i][j] &= \min \left\{ \text{costo}[i][j], \text{costo}[i][k] + \text{costo}[k][j] + \delta \right\} &\text{donde } \delta \in [-5,5] \end{aligned} \end{equation}
3.7 Herramientas y Librerías de Python¶
# Gráficos, Datos y Cálculos
import numpy as np # Matrcies
import matplotlib.pyplot as plt # graficos
import seaborn as sns # Graficos elaborados
import plotly.express as px # Graficos interactivos
import matplotlib.ticker as ticker # configurar la localización y el formato de los ticks (marcas) en los ejes
import math # Para el manejo de infinito
import pandas as pd # Manejo de datasets
import json # manejos archivos complejos
# Programación en PARALELO
import os # Interacción con el sistema operativo
import psutil # Monitoreo de recursos del sistema
import tracemalloc # Seguimiento de uso de memoria
from joblib import Parallel, delayed # Ejecución paralela de tareas
# Gestión de Memoria y Tiempo t pruebas unitarias
import random # Importa el módulo random para generar números aleatorios
import unittest # Para pruebas unitarias (Framework)
import time # Para medir el tiempo
# Estadística
import statsmodels.api as sm # Módulo principal de statsmodels para realizar análisis estadísticos como regresión, modelos lineales, pruebas estadísticas, etc.
from statsmodels.formula.api import ols # Para ajustar modelos de regresión lineal usando fórmulas estilo R
from statsmodels.stats.multicomp import pairwise_tukeyhsd # realizar la prueba de comparaciones múltiples de Tukey entre grupos.
from scipy.stats import ttest_ind # Para realizar la prueba t de Student para comparar dos muestras independientes.
# Machine Learning
from sklearn.preprocessing import OneHotEncoder # Variables categóricas
from sklearn.preprocessing import StandardScaler # Escalamiento de datos
from sklearn.model_selection import train_test_split # Data splitting
from sklearn.ensemble import RandomForestRegressor # modelo de regresión de bosque aleatorio, que utiliza múltiples árboles de decisión para hacer predicciones
from sklearn.ensemble import RandomForestClassifier # modelo de clasificación de bosque aleatorio
from sklearn.metrics import mean_absolute_error, r2_score, classification_report, accuracy_score # Métricas de evaluación
from google.colab import drive # Conectarse al drive, para cargar los archivos json generados
drive.mount('/content/drive')
Mounted at /content/drive
4. Implementación en Python:¶
4.1 Funciones para Generar Instancias¶
Instancias uniforme y estructurada.¶
def generar_instancia_uniforme(n, low=1, high=10, seed=None):
"""
Genera una matriz de costos de dimensiones (n+1) x (n+1).
Para cada par (i, j) con i < j, asigna un valor entero aleatorio en el rango [low, high].
"""
if seed is not None: # Verifica si se ha proporcionado una semilla para la aleatoriedad
random.seed(seed) # Si es así, establece la semilla para garantizar reproducibilidad
# Crea una matriz (lista de listas) de tamaño (n+1) x (n+1) inicializada en 0
costo = [[0] * (n+1) for _ in range(n+1)]
# Itera sobre los índices de fila desde 1 hasta n-1 (se omite la fila 0)
for i in range(1, n):
# Para cada fila i, itera sobre los índices de columna desde i+1 hasta n
for j in range(i+1, n+1):
# Asigna un costo aleatorio entero entre low y high al par (i, j)
costo[i][j] = random.randint(low, high)
return costo
def generar_instancia_estructurada(n, low=1, high=10, seed=None):
"""
Genera una matriz de costos pseudo-aditiva con dos fases:
1) Inicialización: Se asigna un valor entero aleatorio en [low, high] para cada par (i, j) con i < j.
2) Refinamiento: Se ajustan los costos considerando rutas indirectas y añadiendo un delta aleatorio en [-5, 5].
"""
if seed is not None:
random.seed(seed)
costo = [[0] * (n+1) for _ in range(n+1)]
# Paso 1: Inicialización básica de la matriz de costos
for i in range(1, n):
for j in range(i+1, n+1): # Itera para cada puerto j que es mayor que i
# Asigna un costo aleatorio entero entre low y high al tramo directo (i, j)
costo[i][j] = random.randint(low, high)
# Paso 2: Refinamiento de la matriz para introducir pseudo-aditividad
for i in range(1, n):
for j in range(i+2, n+1):# Para cada origen i, itera sobre destinos j donde existe al menos un puerto intermedio
for k in range(i+1, j): # Itera sobre todos los posibles puertos intermedios entre i y j
# Genera un delta aleatorio entero en el rango [-25, 25]
delta = random.randint(-5, 5)
# Calcula el costo posible de la ruta indirecta pasando por k
posible = costo[i][k] + costo[k][j] + delta
# Si el costo indirecto es menor que el costo directo actual, se actualiza
if posible < costo[i][j]:
# Se asegura que el costo actualizado no sea menor que 1
costo[i][j] = max(1, posible)
return costo
def generar_instancias_globales(categories_dict, tipos_instancia, num_replicas, seed_list):
"""
Genera todas las instancias de costos de antemano, asociadas a semillas únicas.
Retorna:
list: Lista de diccionarios con estructura:
{
'category': str,
'n': int,
'tipo_instancia': str,
'replica_id': int,
'seed': int,
'costo': list(list(int))
}
"""
instancias = []
exp_counter = 0
for category_name, list_n in categories_dict.items():
for n in list_n:
for tipo in tipos_instancia:
for r in range(num_replicas):
seed = seed_list[exp_counter % len(seed_list)]
exp_counter += 1
if tipo == "uniforme":
costo = generar_instancia_uniforme(n, seed=seed)
elif tipo == "estructurada":
costo = generar_instancia_estructurada(n, seed=seed)
else:
raise ValueError("Tipo de instancia no válido.")
instancias.append({
'category': category_name,
'n': n,
'tipo_instancia': tipo,
'replica_id': r,
'seed': seed,
'costo': costo
})
return instancias
Instancias en PARALELO¶
import numpy as np
import random
import json
from joblib import Parallel, delayed
def generar_instancia_uniforme(n, low=1, high=10, seed=None):
"""
Genera una matriz de costos (n+1)x(n+1) para la instancia "uniforme".
Para cada par (i, j) con i >= 1 y j > i se asigna un valor aleatorio entero en [low, high].
Se utiliza vectorización con NumPy para mayor rendimiento.
"""
if seed is not None:
np.random.seed(seed)
# Crear una matriz de ceros
costo = np.zeros((n+1, n+1), dtype=int)
# Obtener los índices del triángulo superior (excluyendo la fila 0)
rows, cols = np.triu_indices(n+1, k=1)
mask = rows >= 1 # ignorar la fila 0
rows, cols = rows[mask], cols[mask]
# Asignar valores aleatorios a los elementos de la parte superior
costo[rows, cols] = np.random.randint(low, high + 1, size=len(rows))
return costo.tolist()
def generar_instancia_estructurada(n, low=1, high=10, seed=None):
"""
Genera una matriz de costos (n+1)x(n+1) para la instancia "estructurada".
Se procede en dos fases:
1. Inicialización: se asigna un valor aleatorio entero en [low, high] a cada par (i, j) con i>=1 y j>i.
2. Refinamiento: para cada par (i,j) se exploran rutas indirectas (pasando por un k intermedio)
y se ajusta el costo si se encuentra una ruta más barata, sumándole un delta aleatorio en [-5, 5].
La inicialización se vectoriza, pero el refinamiento se realiza con bucles.
"""
if seed is not None:
np.random.seed(seed)
costo = np.zeros((n+1, n+1), dtype=int)
# Fase 1: Inicialización vectorizada (ignorar la fila 0)
rows, cols = np.triu_indices(n+1, k=1)
mask = rows >= 1
rows, cols = rows[mask], cols[mask]
costo[rows, cols] = np.random.randint(low, high + 1, size=len(rows))
# Fase 2: Refinamiento (exploración de rutas indirectas)
for i in range(1, n):
for j in range(i+2, n+1):
for k in range(i+1, j):
# delta aleatorio entre -5 y 5 (incluidos)
delta = np.random.randint(-5, 6)
posible = costo[i][k] + costo[k][j] + delta
if posible < costo[i][j]:
costo[i][j] = max(1, posible)
return costo.tolist()
def generar_instancias_por_combinacion(category_name, n, tipo, num_replicas, seed_list):
"""
Genera todas las réplicas para una combinación de (categoría, n, tipo de instancia).
Se itera internamente sobre el número de réplicas, asignando una semilla de la lista.
"""
instancias = []
for replica in range(num_replicas):
# Selecciona una semilla cíclicamente de seed_list
seed = seed_list[replica % len(seed_list)]
if tipo == "uniforme":
costo = generar_instancia_uniforme(n, seed=seed)
elif tipo == "estructurada":
costo = generar_instancia_estructurada(n, seed=seed)
else:
raise ValueError("Tipo de instancia no válido: {}".format(tipo))
instancias.append({
'category': category_name,
'n': n,
'tipo_instancia': tipo,
'replica_id': replica,
'seed': seed,
'costo': costo
})
return instancias
def generar_instancias_globales_parallel(categories_dict, tipos_instancia, num_replicas, seed_list):
"""
Genera todas las instancias de forma paralela agrupando por cada combinación de:
- Categoría (clave en categories_dict)
- Tamaño n (valor en la lista asociada a la categoría)
- Tipo de instancia (por ejemplo, 'uniforme' o 'estructurada')
Se utiliza joblib.Parallel para distribuir la generación de las réplicas de cada combinación.
"""
tasks = []
for category_name, list_n in categories_dict.items():
for n in list_n:
for tipo in tipos_instancia:
tasks.append((category_name, n, tipo))
# Paralelizar sobre cada combinación (reduciendo la sobrecarga al evitar tareas muy pequeñas)
resultados = Parallel(n_jobs=-1)(
delayed(generar_instancias_por_combinacion)(cat, n, tipo, num_replicas, seed_list)
for (cat, n, tipo) in tasks
)
# Aplanar la lista de listas en una sola lista de instancias
instancias = [inst for sublist in resultados for inst in sublist]
return instancias
if __name__ == '__main__':
# Parámetros de ejemplo
CATEGORIES = {
"XS": [4, 5, 7, 10, 14],
"S": [15, 18, 20, 22, 24],
"M": [25, 30, 35, 40, 45],
"L": [50, 60, 70, 80, 90],
"XL": [100, 120, 150, 200, 400]
}
tipos_instancia = ['uniforme', 'estructurada']
num_replicas = 50
# Generar una lista de semillas aleatorias
seed_list = [random.randint(0, 999999) for _ in range(100)]
# Generar todas las instancias en paralelo
instancias = generar_instancias_globales_parallel(CATEGORIES, tipos_instancia, num_replicas, seed_list)
# Guardar el resultado en un archivo JSON
with open('instancias_parallel.json', 'w') as f:
json.dump(instancias, f, default=str)
print("Instancias guardadas en 'instancias_parallel.json'")
Instancias guardadas en 'instancias_parallel.json'
4.2 Algoritmos a Comparar¶
def fuerza_bruta_recursivo(costo, i, n):
"""
Implementa la estrategia recursiva sin memoización para el Problema de Alquiler de Canoas.
Explora todas las rutas posibles de manera exhaustiva.
Parámetros:
- costo: matriz de costos (dimensiones (n+1) x (n+1)), donde costo[i][j] es el costo de ir del puerto i al j.
- i: puerto de origen actual.
- n: número total de puertos.
Retorna:
- Costo mínimo acumulado desde el puerto i hasta el puerto n.
"""
if i >= n: # Maneja i > n (casos con 0 o 1 puerto) ✅
return 0 # Caso base: si se llega al último puerto, no se requiere costo adicional.
min_cost = math.inf # Inicializa el costo mínimo con infinito.
for j in range(i+1, n+1): # Explora todos los puertos siguientes (i+1 a n).
actual = costo[i][j] + fuerza_bruta_recursivo(costo, j, n)
if actual < min_cost:
min_cost = actual
return min_cost
def recursivo_con_memo(costo, i, n, memo):
"""
Variante optimizada de la recursión que almacena resultados intermedios para evitar recomputaciones.
Parámetros:
- costo: matriz de costos.
- i: puerto de origen actual.
- n: número total de puertos.
- memo: lista de tamaño (n+1) para almacenar el costo mínimo ya calculado para cada puerto.
Retorna:
- Costo mínimo acumulado desde el puerto i hasta el puerto n.
"""
if i >= n: # Caso base. Pero Maneja i >= n (casos con 0 o 1 puerto) ✅
return 0
if memo[i] is not None:
return memo[i] # Retorna el resultado ya calculado para el puerto i.
min_cost = math.inf
for j in range(i+1, n+1):
actual = costo[i][j] + recursivo_con_memo(costo, j, n, memo)
if actual < min_cost:
min_cost = actual
memo[i] = min_cost # Guarda el resultado para el puerto i.
return min_cost
def recursivo_con_memo_wrapper(costo, n):
"""
Inicializa la tabla de memoización y llama a la función recursiva optimizada.
Parámetros:
- costo: matriz de costos.
- n: número total de puertos.
Retorna:
- Costo mínimo desde el puerto 1 hasta el puerto n.
"""
if n == 0: # Caso especial: no hay puertos destino ✅
return 0
memo = [None] * (n+1) # Crea una lista para almacenar resultados de subproblemas.
return recursivo_con_memo(costo, 1, n, memo)
def programacion_dinamica(costo, n):
"""
Resuelve el problema de forma iterativa, comenzando desde el último puerto hasta el primero.
Parámetros:
- costo: matriz de costos.
- n: número total de puertos.
Retorna:
- Costo mínimo desde el puerto 1 hasta el puerto n.
"""
if n == 0: # Caso especial: no hay puertos destino ✅
return 0
dp = [0] * (n+1)
dp[n] = 0 # Caso base: costo 0 al llegar al último puerto.
for i in range(n-1, 0, -1): # Itera desde n-1 hasta 1.
dp[i] = math.inf # Inicializa con infinito.
for j in range(i+1, n+1):
actual = costo[i][j] + dp[j]
if actual < dp[i]:
dp[i] = actual
return dp[1]
4.3 Pruebas Unitarias¶
class TestAlgoritmosCanoas(unittest.TestCase):
"""
Conjunto exhaustivo de pruebas unitarias para los algoritmos del Problema de Alquiler de Canoas.
Cubre casos bordes, mínimos, estructurados y no estructurados, validando correctitud y robustez.
"""
# --------------------------
# Casos Bordes y Mínimos
# --------------------------
def test_n0_0_puertos(self):
"""Caso borde: 0 puertos destino (solo el inicial)."""
costo = [[0]] # Matriz 1x1 (n=0)
n = 0
self._ejecutar_pruebas(costo, n, 0)
def test_n1_1_puerto(self):
"""Caso borde: 1 puerto (inicio = fin)."""
costo = [[0, 0],
[0, 0]] # Matriz 2x2 (n=1)
n = 1
self._ejecutar_pruebas(costo, n, 0)
def test_n2_2_puertos(self):
"""Caso mínimo no trivial: 2 puertos (ruta directa única)."""
costo = [
[0, 0, 0],
[0, 0, 5], # 1→2
[0, 0, 0]
]
n = 2
self._ejecutar_pruebas(costo, n, 5)
# --------------------------
# Casos con Estructura Aditiva
# --------------------------
def test_n3_ruta_optima_no_directa(self):
"""Ruta óptima requiere múltiples saltos (1→2→3)."""
costo = [
[0, 0, 0, 0],
[0, 0, 2, 10], # 1→3=10
[0, 0, 0, 3], # 2→3=3
[0, 0, 0, 0]
]
n = 3
self._ejecutar_pruebas(costo, n, 5) # 2+3=5
def test_n4_ruta_optima_multiple_saltos(self):
"""Caso clásico con 4 puertos y ruta óptima en 3 saltos (1→2→3→4)."""
costo = [
[0, 0, 0, 0, 0],
[0, 0, 2, 5, 9], # 1→4=9
[0, 0, 0, 2, 4], # 2→4=4
[0, 0, 0, 0, 2], # 3→4=2
[0, 0, 0, 0, 0]
]
n = 4
self._ejecutar_pruebas(costo, n, 6) # 2+2+2=6
# --------------------------
# Casos con Estructura Pseudo-Aditiva
# --------------------------
def test_n4_estructura_pseudo_aditiva(self):
"""Costo mínimo con 'delta negativo' simulado (1→2→3→4 = 1+1+1=3)."""
costo = [
[0, 0, 0, 0, 0],
[0, 0, 1, 5, 10], # 1→4=10
[0, 0, 0, 1, 3], # 2→4=3
[0, 0, 0, 0, 1], # 3→4=1
[0, 0, 0, 0, 0]
]
n = 4
self._ejecutar_pruebas(costo, n, 3)
# --------------------------
# Casos con Rutas Directas Óptimas
# --------------------------
def test_n3_ruta_directa_optima(self):
"""Camino directo es óptimo (1→3=15 vs 1→2→3=20)."""
costo = [
[0, 0, 0, 0],
[0, 0, 10, 15], # 1→3=15
[0, 0, 0, 10], # 2→3=10
[0, 0, 0, 0]
]
n = 3
self._ejecutar_pruebas(costo, n, 15)
# --------------------------
# Casos de Mayor Escala (Stress)
# --------------------------
def test_n5_complejidad_creciente(self):
"""Caso con 5 puertos y estructura jerárquica."""
costo = [
[0, 0, 0, 0, 0, 0],
[0, 0, 2, 5, 9, 20], # 1→5=20
[0, 0, 0, 2, 4, 7], # 2→5=7
[0, 0, 0, 0, 2, 5], # 3→5=5
[0, 0, 0, 0, 0, 3], # 4→5=3
[0, 0, 0, 0, 0, 0]
]
n = 5
self._ejecutar_pruebas(costo, n, 9) # 1→2→3→4→5 = 2+2+2+3=9 ❌ ¿Error? ¡Validar!
# --------------------------
# Método Auxiliar
# --------------------------
def _ejecutar_pruebas(self, costo, n, expected):
"""Ejecuta los tres algoritmos y verifica el resultado esperado."""
# Fuerza Bruta Recursivo
result_fb = fuerza_bruta_recursivo(costo, 1, n)
self.assertEqual(result_fb, expected, f"Fuerza Bruta falló: {result_fb} != {expected}")
# Recursivo con Memoización
result_memo = recursivo_con_memo_wrapper(costo, n)
self.assertEqual(result_memo, expected, f"Memoización falló: {result_memo} != {expected}")
# Programación Dinámica
result_dp = programacion_dinamica(costo, n)
self.assertEqual(result_dp, expected, f"Programación Dinámica falló: {result_dp} != {expected}")
if __name__ == '__main__':
unittest.main(argv=[''], exit=False)
........ ---------------------------------------------------------------------- Ran 8 tests in 0.008s OK
La solución propuesta es correcta, ya que al modificar la condición de parada a if i >= n: return 0, se garantiza el manejo seguro de casos borde (cuando $n \leq 1$). Esto evita el acceso a índices fuera del rango en la matriz de costos, retornando 0 en situaciones donde no existe un trayecto válido, y asegurando así la robustez de la función en escenarios de entrada mínima.
4.4 Función Principal de Experimentos¶
Creación (lectura) Json de instancias:¶
# Se utiliza el módulo json para preservar la estructura original de lista de diccionarios.
# Y se importa con la previa ejecución de la función generar_instancias_globales
with open('/content/drive/MyDrive/UNAL/Semestre IV/Análisis y diseño de Algoritmos/Proyecto/instancias_50.json', 'r') as f:
instancias = json.load(f)
Funciones auxiliares:¶
# Para que se compatible con la programación en paralelo, ya que no admite el lambda
def fuerza_bruta_rec_func(costo, n):
return fuerza_bruta_recursivo(costo, 1, n)
# Los tres algoritmos a usar en el gran for incluyendo fuerza_bruta_rec_func
ALG_FUNC = {
'fuerza_bruta_rec': fuerza_bruta_rec_func,
'rec_con_memo': recursivo_con_memo_wrapper,
'prog_dinamica': programacion_dinamica
}
# Función que mide la memoria de programación en paralelo con
def medir_memoria():
"""
Retorna el uso de memoria (RSS) del proceso actual en MB.
"""
process = psutil.Process(os.getpid())
mem_bytes = process.memory_info().rss
return mem_bytes / (1024 * 1024)
Función que ejcuta todas las instancias con joblib¶
Experimentos usando psutil para memoria¶
def ejecutar_experimento(instancia, algoritmos, skip_large_for_exponential=True):
resultados = []
category_name = instancia['category']
n = instancia['n']
tipo = instancia['tipo_instancia']
r = instancia['replica_id']
costo = instancia['costo']
for alg_name, alg_func in algoritmos.items():
# Salta el algoritmo costoso si la instancia es grande
if skip_large_for_exponential and alg_name in ["fuerza_bruta_rec"] and n >= 15:
resultados.append({
'language': "Python",
'category_size': category_name,
'n': n,
'tipo_instancia': tipo,
'algoritmo': alg_name,
'replica_id': r,
'tiempo_ejecucion': None,
'memoria_max_mb': None,
'costo_minimo': None,
'status': "skipped_due_to_large_n"
})
continue
mem_inicial = medir_memoria()
t0 = time.perf_counter_ns()
resultado = alg_func(costo, n)
t1 = time.perf_counter_ns()
mem_final = medir_memoria()
tiempo = t1 - t0
# Calculamos la diferencia de memoria entre el inicio y el fin
mem_peak = mem_final - mem_inicial if mem_final >= mem_inicial else 0.0
resultados.append({
'language': "Python",
'category_size': category_name,
'n': n,
'tipo_instancia': tipo,
'algoritmo': alg_name,
'replica_id': r,
'tiempo_ejecucion': tiempo,
'memoria_max_mb': mem_peak,
'costo_minimo': resultado,
'status': "ok"
})
return resultados
t1 = time.perf_counter_ns()
if __name__ == '__main__':
# Ejecutar los experimentos en paralelo utilizando el backend "multiprocessing"
all_results_paralelos = Parallel(n_jobs=-1, backend="multiprocessing")(
delayed(ejecutar_experimento)(instancia, ALG_FUNC) for instancia in instancias
)
# Aplanar la lista de listas en una única lista de resultados:
# Cada llamada a ejecutar_experimento retorna una lista de diccionarios y all_results_paralelos es una lista de estas listas.
all_results = [resultado for sublista in all_results_paralelos for resultado in sublista]
# Convertir la lista de diccionarios en un DataFrame para facilitar el análisis y almacenamiento
df_resultados = pd.DataFrame(all_results)
# Guardar el DataFrame en un archivo CSV
df_resultados.to_csv("resultados_optimizados.csv", index=False)
print("Resultados guardados en 'resultados_optimizados.csv'")
t2 = time.perf_counter_ns()
print(f"Tiempo de ejecución: {(t2 - t1) / 1e9} segundos")
Experimentos usando tracemalloc para memoria¶
def ejecutar_experimento2(instancia, algoritmos, skip_large_for_exponential=True):
resultados = []
category_name = instancia['category']
n = instancia['n']
tipo = instancia['tipo_instancia']
r = instancia['replica_id']
costo = instancia['costo']
for alg_name, alg_func in algoritmos.items():
# Salta el algoritmo costoso si la instancia es grande
if skip_large_for_exponential and alg_name in ["fuerza_bruta_rec"] and n >= 15:
resultados.append({
'language': "Python",
'category_size': category_name,
'n': n,
'tipo_instancia': tipo,
'algoritmo': alg_name,
'replica_id': r,
'tiempo_ejecucion': None,
'memoria_max_mb': None,
'costo_minimo': None,
'status': "skipped_due_to_large_n"
})
continue
# Inicia tracemalloc para rastrear asignaciones de memoria
tracemalloc.start()
t0 = time.perf_counter_ns()
resultado = alg_func(costo, n)
t1 = time.perf_counter_ns()
# Obtiene la memoria actual y el pico durante la ejecución
current, peak = tracemalloc.get_traced_memory()
tracemalloc.stop()
tiempo = t1 - t0
# Convertir el pico de memoria de bytes a MB
mem_peak_mb = peak / (1024 * 1024)
resultados.append({
'language': "Python",
'category_size': category_name,
'n': n,
'tipo_instancia': tipo,
'algoritmo': alg_name,
'replica_id': r,
'tiempo_ejecucion': tiempo,
'memoria_max_mb': mem_peak_mb,
'costo_minimo': resultado,
'status': "ok"
})
return resultados
ti = time.perf_counter_ns()
if __name__ == '__main__':
# Ejecutar los experimentos en paralelo utilizando todos los núcleos disponibles
# Forzamos el backend "multiprocessing" para mayor compatibilidad
all_results_paralelos = Parallel(n_jobs=-1, backend="multiprocessing")(
delayed(ejecutar_experimento2)(instancia, ALG_FUNC) for instancia in instancias
)
# Aplanar la lista de listas en una única lista de resultados:
# Cada llamada a ejecutar_experimento retorna una lista de diccionarios (uno por algoritmo)
all_results = [resultado for sublista in all_results_paralelos for resultado in sublista]
# Convertir la lista de diccionarios en un DataFrame para análisis y almacenamiento
df_resultados = pd.DataFrame(all_results)
# Guardar el DataFrame en un archivo CSV
df_resultados.to_csv("resultados_optimizados2.csv", index=False)
print("Resultados guardados en 'resultados_optimizados2.csv'")
tf = time.perf_counter_ns()
print(f"Tiempo de ejecución: {(tf - ti) / 1e9} segundos")
5. Análisis Estadístico y Validación de Hipótesis¶
**5.1 Estadística Descriptiva usando **psutil****¶
# El archivo "resultados_optimizados.csv" es el más grande usado convertido
# del json de 80 MB con 50 réplicas en todos los tamaño y cargamos el usó:
# psutil, para medir memoria, sin embargo veamos las diferencias:
df = pd.read_csv("resultados_optimizados.csv")
df.head() # primeras 5 filas del dataset
| language | category_size | n | tipo_instancia | algoritmo | replica_id | tiempo_ejecucion | memoria_max_mb | costo_minimo | status | |
|---|---|---|---|---|---|---|---|---|---|---|
| 0 | Python | XS | 4 | uniforme | fuerza_bruta_rec | 0 | 48840.0 | 0.0 | 8.0 | ok |
| 1 | Python | XS | 4 | uniforme | rec_con_memo | 0 | 31924.0 | 0.0 | 8.0 | ok |
| 2 | Python | XS | 4 | uniforme | prog_dinamica | 0 | 19215.0 | 0.0 | 8.0 | ok |
| 3 | Python | XS | 4 | uniforme | fuerza_bruta_rec | 1 | 48948.0 | 0.0 | 5.0 | ok |
| 4 | Python | XS | 4 | uniforme | rec_con_memo | 1 | 28295.0 | 0.0 | 5.0 | ok |
df['status'].value_counts() # cuántos experimentos no pasaron por ser fuerza_bruta_recursiva
| count | |
|---|---|
| status | |
| ok | 5500 |
| skipped_due_to_large_n | 2000 |
df['memoria_max_mb'].value_counts() # contar los valores almacenados en la memoria
| count | |
|---|---|
| memoria_max_mb | |
| 0.000359 | 207 |
| 0.000214 | 200 |
| 0.000252 | 130 |
| 0.000519 | 102 |
| 0.001320 | 101 |
| ... | ... |
| 0.001747 | 1 |
| 0.001213 | 1 |
| 0.002815 | 1 |
| 0.002014 | 1 |
| 0.000946 | 1 |
69 rows × 1 columns
df.info() # Información de los valores nulos
<class 'pandas.core.frame.DataFrame'> RangeIndex: 7500 entries, 0 to 7499 Data columns (total 10 columns): # Column Non-Null Count Dtype --- ------ -------------- ----- 0 language 7500 non-null object 1 category_size 7500 non-null object 2 n 7500 non-null int64 3 tipo_instancia 7500 non-null object 4 algoritmo 7500 non-null object 5 replica_id 7500 non-null int64 6 tiempo_ejecucion 5500 non-null float64 7 memoria_max_mb 5500 non-null float64 8 costo_minimo 5500 non-null float64 9 status 7500 non-null object dtypes: float64(3), int64(2), object(5) memory usage: 586.1+ KB
# Filtrar filas skip para quedarse solo con los valores no null
df_ok = df[df['status'] == 'ok']
df_ok.head()
| language | category_size | n | tipo_instancia | algoritmo | replica_id | tiempo_ejecucion | memoria_max_mb | costo_minimo | status | |
|---|---|---|---|---|---|---|---|---|---|---|
| 0 | Python | XS | 4 | uniforme | fuerza_bruta_rec | 0 | 48840.0 | 0.0 | 8.0 | ok |
| 1 | Python | XS | 4 | uniforme | rec_con_memo | 0 | 31924.0 | 0.0 | 8.0 | ok |
| 2 | Python | XS | 4 | uniforme | prog_dinamica | 0 | 19215.0 | 0.0 | 8.0 | ok |
| 3 | Python | XS | 4 | uniforme | fuerza_bruta_rec | 1 | 48948.0 | 0.0 | 5.0 | ok |
| 4 | Python | XS | 4 | uniforme | rec_con_memo | 1 | 28295.0 | 0.0 | 5.0 | ok |
df_ok.info() # Para observar los valores no null
<class 'pandas.core.frame.DataFrame'> Index: 5500 entries, 0 to 7499 Data columns (total 10 columns): # Column Non-Null Count Dtype --- ------ -------------- ----- 0 language 5500 non-null object 1 category_size 5500 non-null object 2 n 5500 non-null int64 3 tipo_instancia 5500 non-null object 4 algoritmo 5500 non-null object 5 replica_id 5500 non-null int64 6 tiempo_ejecucion 5500 non-null float64 7 memoria_max_mb 5500 non-null float64 8 costo_minimo 5500 non-null float64 9 status 5500 non-null object dtypes: float64(3), int64(2), object(5) memory usage: 472.7+ KB
# 1) Descripción general en TIEMPO
desc_tiempos = df_ok.groupby(['n','algoritmo'])['tiempo_ejecucion'].describe()
print(desc_tiempos)
count mean std min \
n algoritmo
4 fuerza_bruta_rec 100.0 61704.53 5.219786e+05 5507.0
prog_dinamica 100.0 8333.15 6.414380e+03 4822.0
rec_con_memo 100.0 9252.39 6.323947e+03 4969.0
5 fuerza_bruta_rec 100.0 71704.46 6.040627e+05 7719.0
prog_dinamica 100.0 7446.58 2.076783e+03 4761.0
rec_con_memo 100.0 9050.13 3.311368e+03 5598.0
7 fuerza_bruta_rec 100.0 89655.76 3.679048e+05 23834.0
prog_dinamica 100.0 10246.46 4.539836e+03 6740.0
rec_con_memo 100.0 12467.79 2.885704e+03 8355.0
10 fuerza_bruta_rec 100.0 599048.61 1.808224e+06 175242.0
prog_dinamica 100.0 14550.88 7.014820e+03 10125.0
rec_con_memo 100.0 123796.30 1.046334e+06 13691.0
14 fuerza_bruta_rec 100.0 9057766.59 4.656391e+06 3327855.0
prog_dinamica 100.0 43125.05 2.022890e+05 16718.0
rec_con_memo 100.0 93367.33 4.079445e+05 25983.0
15 prog_dinamica 100.0 126053.13 1.004272e+06 19106.0
rec_con_memo 100.0 40318.71 1.251392e+04 30638.0
18 prog_dinamica 100.0 89232.20 3.298731e+05 24041.0
rec_con_memo 100.0 57819.33 3.208278e+04 42961.0
20 prog_dinamica 100.0 123894.15 5.608442e+05 27859.0
rec_con_memo 100.0 459493.91 2.336477e+06 52514.0
22 prog_dinamica 100.0 427687.16 2.134244e+06 36750.0
rec_con_memo 100.0 694744.09 2.778932e+06 63002.0
24 prog_dinamica 100.0 410099.93 1.520223e+06 38795.0
rec_con_memo 100.0 275771.42 7.922631e+05 72982.0
25 prog_dinamica 100.0 192688.12 6.400553e+05 46350.0
rec_con_memo 100.0 655389.19 1.633963e+06 69245.0
30 prog_dinamica 100.0 242661.98 9.610361e+05 66110.0
rec_con_memo 100.0 882480.41 2.536709e+06 118015.0
35 prog_dinamica 100.0 409636.27 1.731741e+06 74558.0
rec_con_memo 100.0 607265.15 1.722300e+06 146013.0
40 prog_dinamica 100.0 445079.86 1.542429e+06 89280.0
rec_con_memo 100.0 1500023.71 2.922949e+06 194345.0
45 prog_dinamica 100.0 1097216.13 3.287741e+06 109536.0
rec_con_memo 100.0 1244409.70 2.954315e+06 210243.0
50 prog_dinamica 100.0 586384.54 1.797410e+06 151026.0
rec_con_memo 100.0 826856.70 1.301032e+06 303578.0
60 prog_dinamica 100.0 392000.90 8.465907e+05 180488.0
rec_con_memo 100.0 831116.31 1.249806e+06 443455.0
70 prog_dinamica 100.0 524833.23 8.663803e+05 247990.0
rec_con_memo 100.0 1942961.03 1.993512e+06 709918.0
80 prog_dinamica 100.0 1205857.18 2.358562e+06 329100.0
rec_con_memo 100.0 4043713.56 4.991925e+06 1008685.0
90 prog_dinamica 100.0 948280.36 1.405468e+06 396132.0
rec_con_memo 100.0 3889019.50 4.498740e+06 1238241.0
100 prog_dinamica 100.0 2155701.88 3.985881e+06 577108.0
rec_con_memo 100.0 6713591.42 6.175403e+06 1864553.0
120 prog_dinamica 100.0 3637851.53 4.192951e+06 809389.0
rec_con_memo 100.0 11947287.01 7.492544e+06 2774833.0
150 prog_dinamica 100.0 6280899.77 5.792716e+06 1220840.0
rec_con_memo 100.0 22976257.45 8.975174e+06 4583720.0
200 prog_dinamica 100.0 8394005.30 5.891054e+06 2318280.0
rec_con_memo 100.0 28131455.02 1.038191e+07 9591498.0
400 prog_dinamica 100.0 25067883.12 1.117707e+07 9294587.0
rec_con_memo 100.0 91303845.44 2.925778e+07 35085738.0
25% 50% 75% max
n algoritmo
4 fuerza_bruta_rec 6579.50 7361.0 9.437000e+03 5228593.0
prog_dinamica 5747.00 6749.0 7.851000e+03 54548.0
rec_con_memo 6347.75 7268.5 9.537750e+03 48364.0
5 fuerza_bruta_rec 10066.25 10835.5 1.173925e+04 6051870.0
prog_dinamica 6265.75 7002.5 7.829000e+03 18523.0
rec_con_memo 7277.00 8140.5 9.291750e+03 28782.0
7 fuerza_bruta_rec 30918.00 32805.5 3.436600e+04 3077909.0
prog_dinamica 9004.00 9525.0 1.015525e+04 47312.0
rec_con_memo 11261.50 11928.0 1.259325e+04 27957.0
10 fuerza_bruta_rec 209965.50 235184.5 2.540158e+05 10855554.0
prog_dinamica 12984.00 13800.0 1.460550e+04 77830.0
rec_con_memo 17592.00 19033.0 1.982650e+04 10482421.0
14 fuerza_bruta_rec 6633096.00 8484838.0 1.070574e+07 34759270.0
prog_dinamica 20798.25 22484.5 2.321525e+04 2045099.0
rec_con_memo 32705.25 35018.0 3.739375e+04 3133882.0
15 prog_dinamica 21793.50 23061.0 2.462275e+04 10067714.0
rec_con_memo 34861.25 37358.5 3.943450e+04 134854.0
18 prog_dinamica 28780.75 30442.5 3.247525e+04 2077288.0
rec_con_memo 48546.75 51272.5 5.461850e+04 338449.0
20 prog_dinamica 35029.75 36391.0 3.846550e+04 5087460.0
rec_con_memo 60283.00 62661.5 6.709950e+04 17316128.0
22 prog_dinamica 40799.75 42505.0 4.459000e+04 14950097.0
rec_con_memo 72464.75 76367.5 8.079050e+04 17125300.0
24 prog_dinamica 47069.75 49286.5 5.793950e+04 10087121.0
rec_con_memo 84654.75 90671.0 9.742625e+04 7138938.0
25 prog_dinamica 52049.50 53572.5 7.411500e+04 5612727.0
rec_con_memo 97815.75 106070.5 4.118098e+05 10255853.0
30 prog_dinamica 69210.75 72558.5 7.971600e+04 6368526.0
rec_con_memo 134190.00 138289.5 1.476828e+05 14411558.0
35 prog_dinamica 90748.75 92665.5 9.834300e+04 15138351.0
rec_con_memo 177450.25 184611.0 1.968300e+05 11004801.0
40 prog_dinamica 115768.00 120788.5 1.313565e+05 10334988.0
rec_con_memo 229963.50 240018.5 2.565320e+05 12921403.0
45 prog_dinamica 141692.50 149743.0 1.627680e+05 22139272.0
rec_con_memo 284878.75 300001.0 3.153990e+05 20453304.0
50 prog_dinamica 175151.25 182002.5 2.112798e+05 13362334.0
rec_con_memo 353023.75 371148.0 4.635205e+05 8223964.0
60 prog_dinamica 235094.25 248504.5 2.608910e+05 5383811.0
rec_con_memo 580844.75 610087.5 6.325818e+05 10583409.0
70 prog_dinamica 319789.00 338987.0 3.547852e+05 7053841.0
rec_con_memo 920175.25 976770.5 2.668450e+06 11443745.0
80 prog_dinamica 421055.75 438301.5 4.677680e+05 13468494.0
rec_con_memo 1320182.25 1372022.5 5.079953e+06 30016718.0
90 prog_dinamica 514104.75 534458.5 5.643522e+05 8652543.0
rec_con_memo 1628564.25 1749333.0 4.737237e+06 31002407.0
100 prog_dinamica 660878.25 702149.5 1.728142e+06 27192531.0
rec_con_memo 2114750.75 4892089.0 9.350509e+06 36134365.0
120 prog_dinamica 973942.25 1151460.5 3.981179e+06 17165842.0
rec_con_memo 5220622.75 10139997.0 1.623446e+07 35221473.0
150 prog_dinamica 1545223.25 3558646.5 1.057733e+07 23208241.0
rec_con_memo 15773881.75 23921804.5 2.941298e+07 42206423.0
200 prog_dinamica 2836731.00 7477735.5 1.072993e+07 37967637.0
rec_con_memo 20456725.00 26636828.0 3.445102e+07 68158565.0
400 prog_dinamica 17523201.75 23917694.5 3.151054e+07 59705813.0
rec_con_memo 71585465.00 91686394.5 1.118647e+08 151425091.0
# 1.1) Descripción más específica en TIEMPO
desc_tiempos_especificos = df_ok.groupby(['category_size','algoritmo', 'tipo_instancia'])['tiempo_ejecucion'].describe()
print(desc_tiempos_especificos)
count mean \
category_size algoritmo tipo_instancia
L prog_dinamica estructurada 250.0 7.566642e+05
uniforme 250.0 7.062782e+05
rec_con_memo estructurada 250.0 2.369861e+06
uniforme 250.0 2.243606e+06
M prog_dinamica estructurada 250.0 5.510921e+05
uniforme 250.0 4.038209e+05
rec_con_memo estructurada 250.0 1.191087e+06
uniforme 250.0 7.647399e+05
S prog_dinamica estructurada 250.0 2.986697e+05
uniforme 250.0 1.721169e+05
rec_con_memo estructurada 250.0 3.788323e+05
uniforme 250.0 2.324267e+05
XL prog_dinamica estructurada 250.0 8.509651e+06
uniforme 250.0 9.704886e+06
rec_con_memo estructurada 250.0 3.102510e+07
uniforme 250.0 3.340387e+07
XS fuerza_bruta_rec estructurada 250.0 2.039827e+06
uniforme 250.0 1.912125e+06
prog_dinamica estructurada 250.0 2.063168e+04
uniforme 250.0 1.284917e+04
rec_con_memo estructurada 250.0 5.876844e+04
uniforme 250.0 4.040513e+04
std min \
category_size algoritmo tipo_instancia
L prog_dinamica estructurada 1.578391e+06 151026.0
uniforme 1.597977e+06 153035.0
rec_con_memo estructurada 3.433891e+06 303578.0
uniforme 3.612918e+06 314252.0
M prog_dinamica estructurada 2.155632e+06 46350.0
uniforme 1.587320e+06 48099.0
rec_con_memo estructurada 2.873608e+06 69245.0
uniforme 1.885758e+06 89934.0
S prog_dinamica estructurada 1.430141e+06 20214.0
uniforme 1.136373e+06 19106.0
rec_con_memo estructurada 1.931710e+06 30638.0
uniforme 1.368300e+06 31611.0
XL prog_dinamica estructurada 9.465289e+06 577108.0
uniforme 1.170241e+07 588561.0
rec_con_memo estructurada 3.259128e+07 1963090.0
uniforme 3.545423e+07 1864553.0
XS fuerza_bruta_rec estructurada 4.417220e+06 5507.0
uniforme 3.995924e+06 5808.0
prog_dinamica estructurada 1.287929e+05 4761.0
uniforme 7.684271e+03 5348.0
rec_con_memo estructurada 6.619935e+05 4969.0
uniforme 2.606173e+05 6106.0
25% 50% \
category_size algoritmo tipo_instancia
L prog_dinamica estructurada 250980.25 373424.5
uniforme 240443.75 332175.0
rec_con_memo estructurada 612876.25 1313042.0
uniforme 600230.00 945865.5
M prog_dinamica estructurada 72611.75 97090.5
uniforme 73229.50 99440.5
rec_con_memo estructurada 145410.25 219716.5
uniforme 137216.75 206478.5
S prog_dinamica estructurada 29386.00 37155.0
uniforme 28853.75 37612.0
rec_con_memo estructurada 50026.50 63934.5
uniforme 49148.00 65934.0
XL prog_dinamica estructurada 1026077.00 4669840.5
uniforme 1416859.50 4053184.5
rec_con_memo estructurada 10129861.25 20274569.5
uniforme 8304624.75 21177878.5
XS fuerza_bruta_rec estructurada 10128.50 32545.5
uniforme 10912.50 33329.0
prog_dinamica estructurada 7053.50 9993.0
uniforme 7218.00 10285.5
rec_con_memo estructurada 8226.00 12444.5
uniforme 8609.25 12692.0
75% max
category_size algoritmo tipo_instancia
L prog_dinamica estructurada 505546.00 13362334.0
uniforme 471656.75 13468494.0
rec_con_memo estructurada 2529583.75 31002407.0
uniforme 1760865.25 30016718.0
M prog_dinamica estructurada 139736.00 22139272.0
uniforme 139580.00 15138351.0
rec_con_memo estructurada 296358.50 20453304.0
uniforme 297841.25 12921403.0
S prog_dinamica estructurada 46679.50 13097994.0
uniforme 45998.75 14950097.0
rec_con_memo estructurada 85105.25 17316128.0
uniforme 78443.00 12541518.0
XL prog_dinamica estructurada 12350990.00 41645693.0
uniforme 13628970.75 59705813.0
rec_con_memo estructurada 33928007.00 151425091.0
uniforme 37194515.00 142151406.0
XS fuerza_bruta_rec estructurada 254752.00 34759270.0
uniforme 270888.00 31375422.0
prog_dinamica estructurada 14984.00 2045099.0
uniforme 15646.25 77830.0
rec_con_memo estructurada 20085.50 10482421.0
uniforme 20851.75 3133882.0
# 1.3) Descripción más específica en TIEMPO
desc_tiempos_especificos = df_ok.groupby(['category_size','tipo_instancia'])['tiempo_ejecucion'].describe()
print(desc_tiempos_especificos)
count mean std min \
category_size tipo_instancia
L estructurada 500.0 1.563263e+06 2.789096e+06 151026.0
uniforme 500.0 1.474942e+06 2.894779e+06 153035.0
M estructurada 500.0 8.710897e+05 2.557706e+06 46350.0
uniforme 500.0 5.842804e+05 1.750537e+06 48099.0
S estructurada 500.0 3.387510e+05 1.698300e+06 20214.0
uniforme 500.0 2.022718e+05 1.256796e+06 19106.0
XL estructurada 500.0 1.976738e+07 2.649015e+07 577108.0
uniforme 500.0 2.155438e+07 2.891833e+07 588561.0
XS estructurada 750.0 7.064090e+05 2.743759e+06 4761.0
uniforme 750.0 6.551264e+05 2.474280e+06 5348.0
25% 50% 75% max
category_size tipo_instancia
L estructurada 346540.25 540665.5 1370822.25 31002407.0
uniforme 330495.25 520558.5 1034435.25 30016718.0
M estructurada 95063.75 141733.0 236791.00 22139272.0
uniforme 94506.25 137811.0 232094.75 15138351.0
S estructurada 35559.75 48531.0 72356.25 17316128.0
uniforme 36031.00 47232.0 68547.00 14950097.0
XL estructurada 2820224.25 11507369.0 23742456.50 151425091.0
uniforme 2770063.50 10814184.0 28355439.00 142151406.0
XS estructurada 8182.50 12444.5 31049.00 34759270.0
uniforme 8892.25 13239.5 31287.00 31375422.0
# 2) Descripción general en ESPACIO
desc_espacio = df_ok.groupby(['n','algoritmo'])['memoria_max_mb'].describe()
print(desc_espacio)
count mean std min 25% 50% 75% max
n algoritmo
4 fuerza_bruta_rec 100.0 0.000000 0.000000 0.0 0.0 0.0 0.0 0.000000
prog_dinamica 100.0 0.000000 0.000000 0.0 0.0 0.0 0.0 0.000000
rec_con_memo 100.0 0.000000 0.000000 0.0 0.0 0.0 0.0 0.000000
5 fuerza_bruta_rec 100.0 0.000000 0.000000 0.0 0.0 0.0 0.0 0.000000
prog_dinamica 100.0 0.000000 0.000000 0.0 0.0 0.0 0.0 0.000000
rec_con_memo 100.0 0.000000 0.000000 0.0 0.0 0.0 0.0 0.000000
7 fuerza_bruta_rec 100.0 0.000000 0.000000 0.0 0.0 0.0 0.0 0.000000
prog_dinamica 100.0 0.000000 0.000000 0.0 0.0 0.0 0.0 0.000000
rec_con_memo 100.0 0.000000 0.000000 0.0 0.0 0.0 0.0 0.000000
10 fuerza_bruta_rec 100.0 0.000000 0.000000 0.0 0.0 0.0 0.0 0.000000
prog_dinamica 100.0 0.000000 0.000000 0.0 0.0 0.0 0.0 0.000000
rec_con_memo 100.0 0.000000 0.000000 0.0 0.0 0.0 0.0 0.000000
14 fuerza_bruta_rec 100.0 0.000000 0.000000 0.0 0.0 0.0 0.0 0.000000
prog_dinamica 100.0 0.000000 0.000000 0.0 0.0 0.0 0.0 0.000000
rec_con_memo 100.0 0.000000 0.000000 0.0 0.0 0.0 0.0 0.000000
15 prog_dinamica 100.0 0.000000 0.000000 0.0 0.0 0.0 0.0 0.000000
rec_con_memo 100.0 0.000000 0.000000 0.0 0.0 0.0 0.0 0.000000
18 prog_dinamica 100.0 0.000000 0.000000 0.0 0.0 0.0 0.0 0.000000
rec_con_memo 100.0 0.000000 0.000000 0.0 0.0 0.0 0.0 0.000000
20 prog_dinamica 100.0 0.000000 0.000000 0.0 0.0 0.0 0.0 0.000000
rec_con_memo 100.0 0.000000 0.000000 0.0 0.0 0.0 0.0 0.000000
22 prog_dinamica 100.0 0.000000 0.000000 0.0 0.0 0.0 0.0 0.000000
rec_con_memo 100.0 0.000000 0.000000 0.0 0.0 0.0 0.0 0.000000
24 prog_dinamica 100.0 0.000000 0.000000 0.0 0.0 0.0 0.0 0.000000
rec_con_memo 100.0 0.000000 0.000000 0.0 0.0 0.0 0.0 0.000000
25 prog_dinamica 100.0 0.000000 0.000000 0.0 0.0 0.0 0.0 0.000000
rec_con_memo 100.0 0.000000 0.000000 0.0 0.0 0.0 0.0 0.000000
30 prog_dinamica 100.0 0.000000 0.000000 0.0 0.0 0.0 0.0 0.000000
rec_con_memo 100.0 0.000000 0.000000 0.0 0.0 0.0 0.0 0.000000
35 prog_dinamica 100.0 0.000000 0.000000 0.0 0.0 0.0 0.0 0.000000
rec_con_memo 100.0 0.000000 0.000000 0.0 0.0 0.0 0.0 0.000000
40 prog_dinamica 100.0 0.000000 0.000000 0.0 0.0 0.0 0.0 0.000000
rec_con_memo 100.0 0.000000 0.000000 0.0 0.0 0.0 0.0 0.000000
45 prog_dinamica 100.0 0.000000 0.000000 0.0 0.0 0.0 0.0 0.000000
rec_con_memo 100.0 0.000000 0.000000 0.0 0.0 0.0 0.0 0.000000
50 prog_dinamica 100.0 0.000000 0.000000 0.0 0.0 0.0 0.0 0.000000
rec_con_memo 100.0 0.000000 0.000000 0.0 0.0 0.0 0.0 0.000000
60 prog_dinamica 100.0 0.000000 0.000000 0.0 0.0 0.0 0.0 0.000000
rec_con_memo 100.0 0.003984 0.024686 0.0 0.0 0.0 0.0 0.199219
70 prog_dinamica 100.0 0.000000 0.000000 0.0 0.0 0.0 0.0 0.000000
rec_con_memo 100.0 0.000937 0.008989 0.0 0.0 0.0 0.0 0.089844
80 prog_dinamica 100.0 0.000000 0.000000 0.0 0.0 0.0 0.0 0.000000
rec_con_memo 100.0 0.000000 0.000000 0.0 0.0 0.0 0.0 0.000000
90 prog_dinamica 100.0 0.000000 0.000000 0.0 0.0 0.0 0.0 0.000000
rec_con_memo 100.0 0.002383 0.023828 0.0 0.0 0.0 0.0 0.238281
100 prog_dinamica 100.0 0.000000 0.000000 0.0 0.0 0.0 0.0 0.000000
rec_con_memo 100.0 0.001016 0.010156 0.0 0.0 0.0 0.0 0.101562
120 prog_dinamica 100.0 0.000000 0.000000 0.0 0.0 0.0 0.0 0.000000
rec_con_memo 100.0 0.000000 0.000000 0.0 0.0 0.0 0.0 0.000000
150 prog_dinamica 100.0 0.000000 0.000000 0.0 0.0 0.0 0.0 0.000000
rec_con_memo 100.0 0.000000 0.000000 0.0 0.0 0.0 0.0 0.000000
200 prog_dinamica 100.0 0.000000 0.000000 0.0 0.0 0.0 0.0 0.000000
rec_con_memo 100.0 0.000000 0.000000 0.0 0.0 0.0 0.0 0.000000
400 prog_dinamica 100.0 0.000000 0.000000 0.0 0.0 0.0 0.0 0.000000
rec_con_memo 100.0 0.000000 0.000000 0.0 0.0 0.0 0.0 0.000000
# 2.1) Descripción más específica en ESPACIO
desc_tiempos_especificos = df_ok.groupby(['category_size', 'tipo_instancia'])['memoria_max_mb'].describe()
print(desc_tiempos_especificos)
count mean std min 25% 50% 75% \
category_size tipo_instancia
L estructurada 500.0 0.000508 0.007759 0.0 0.0 0.0 0.0
uniforme 500.0 0.000953 0.013882 0.0 0.0 0.0 0.0
M estructurada 500.0 0.000000 0.000000 0.0 0.0 0.0 0.0
uniforme 500.0 0.000000 0.000000 0.0 0.0 0.0 0.0
S estructurada 500.0 0.000000 0.000000 0.0 0.0 0.0 0.0
uniforme 500.0 0.000000 0.000000 0.0 0.0 0.0 0.0
XL estructurada 500.0 0.000000 0.000000 0.0 0.0 0.0 0.0
uniforme 500.0 0.000203 0.004542 0.0 0.0 0.0 0.0
XS estructurada 750.0 0.000000 0.000000 0.0 0.0 0.0 0.0
uniforme 750.0 0.000000 0.000000 0.0 0.0 0.0 0.0
max
category_size tipo_instancia
L estructurada 0.148438
uniforme 0.238281
M estructurada 0.000000
uniforme 0.000000
S estructurada 0.000000
uniforme 0.000000
XL estructurada 0.000000
uniforme 0.101562
XS estructurada 0.000000
uniforme 0.000000
def plot_tiempo_vs_n(df_ok: pd.DataFrame, title: str = "Tiempo de ejecución promedio vs. n (por algoritmo)\n", palette = 'cubehelix'):
# --- Configuración General ---
sns.set_theme(
style="whitegrid", # Fondo blanco con rejilla sutil
palette= palette, # Paleta de colores "viridis"
font_scale=1.1, # Escala de fuente ligeramente mayor
rc={
"figure.figsize": (6, 4), # Tamaño de la figura
"axes.titlesize": 16, # Tamaño del título
"axes.labelsize": 10, # Tamaño de las etiquetas de los ejes
"xtick.labelsize": 10, # Tamaño de las etiquetas del eje x
"ytick.labelsize": 10, # Tamaño de las etiquetas del eje y
"legend.fontsize": 10, # Tamaño de la fuente de la leyenda
"legend.title_fontsize": 10, # Tamaño del título de la leyenda
"axes.spines.top": False, # Quitar borde superior
"axes.spines.right": False, # Quitar borde derecho
"axes.edgecolor": "0.2", # Color del borde de los ejes (gris oscuro)
"grid.color": "0.8", # Color de la rejilla (gris claro)
"grid.linestyle": "--", # Estilo de línea de la rejilla (discontinua)
"lines.linewidth": 2.5, # Grosor de las líneas
"lines.markersize": 8, # Tamaño de los marcadores
"figure.dpi": 150 # Resolución en puntos por pulgada para la exportación
}
)
# --- Creación del Gráfico ---
plt.figure() # Crear una nueva figura (aunque ya está en rc, es buena práctica)
# Usar lineplot de Seaborn, con intervalos de confianza (desviación estándar)
ax = sns.lineplot(
data=df_ok,
x='n',
y='tiempo_ejecucion',
hue='algoritmo',
style='algoritmo', # Usar diferentes estilos de línea además del color
estimator='mean', # Mostrar la media
errorbar='ci', # Mostrar la desviación estándar como intervalo de confianza "ci", "pi", "se", or "sd"
markers=True, # Mostrar marcadores en los puntos
dashes=False, # Evita que seaborn use líneas discontinuas, controlamos con 'style'
alpha=0.8 # Ligera transparencia para las líneas
)
# --- Personalización del Gráfico ---
ax.set_title(title, fontweight='bold', pad=20) # Título en negrita, con espacio
ax.set_xlabel("Tamaño de entrada (n)", labelpad=12) #Nombre y espacio eje X
ax.set_ylabel("Tiempo de ejecución (ns)", labelpad=12) #Nombre y espacio eje Y
# --- Formato del Eje Y (Científico si es necesario) ---
# Si los tiempos son muy pequeños, usar notación científica
if df_ok['tiempo_ejecucion'].max() < 0.01:
ax.yaxis.set_major_formatter(ticker.ScalarFormatter(useMathText=True))
ax.ticklabel_format(style='sci', axis='y', scilimits=(0, 0))
ax.yaxis.offsetText.set_fontsize(10) # Ajustar tamaño de la notación científica
# --- Leyenda ---
ax.legend(title="Algoritmo", loc="lower right", frameon=True, framealpha=0.9, ncol=1) #Título, ubicación, marco, etc.
#--- Escala Logarítmica (Opcional) ---
# Si quieres una escala logarítmica en el eje y (útil para ver diferencias exponenciales):
ax.set_yscale('log')
ax.set_ylabel("Tiempo de ejecución (ns) - Escala Logarítmica") # Cambiar etiqueta
# --- Ajustes Finales y Mostrar/Guardar ---
plt.tight_layout() # Ajustar automáticamente los márgenes
plt.show()
# Para guardar la figura en alta resolución:
# plt.savefig("tiempo_vs_n.png", dpi=300, bbox_inches='tight') #Ajusta nombre y resolución
# 2) Gráfico de líneas: tiempo vs n
plt.figure(figsize=(6,4))
sns.lineplot(data=df_ok, x='n', y='tiempo_ejecucion', hue='algoritmo',
estimator='mean', markers=True, palette = 'inferno')
plt.title("Tiempo de ejecución promedio vs. n (por algoritmo)\n")
plt.ylabel("Tiempo de ejecución (ns)")
plt.xlabel("Tamaño (n)")
plt.legend()
plt.show()
df_uniforme = df_ok[df_ok['tipo_instancia'] == 'uniforme']
plt.figure(figsize=(6,4))
sns.lineplot(data=df_uniforme, x='n', y='tiempo_ejecucion', hue='algoritmo',
estimator='mean', markers=True, palette = 'inferno')
plt.title("Tiempo de ejecución promedio con instancias \nUNIFORMES vs. n (por algoritmo)\n")
plt.ylabel("Tiempo de ejecución (ns)")
plt.xlabel("Tamaño (n)")
plt.legend()
plt.show()
df_estructurada = df_ok[df_ok['tipo_instancia'] == 'estructurada']
plt.figure(figsize=(6,4))
sns.lineplot(data=df_estructurada, x='n', y='tiempo_ejecucion', hue='algoritmo',
estimator='mean', markers=True, palette = 'inferno')
plt.title("Tiempo de ejecución promedio con instancias\n ESTRUCTURADAS vs. n (por algoritmo)\n")
plt.ylabel("Tiempo de ejecución (ns)")
plt.xlabel("Tamaño (n)")
plt.legend()
plt.show()
# Filtra el DataFrame para incluir solo los algoritmos deseados
df_subset = df_ok[df_ok['algoritmo'].isin(['prog_dinamica', 'rec_con_memo'])]
plt.figure(figsize=(6,4))
sns.lineplot(data=df_subset, x='n', y='tiempo_ejecucion', hue='algoritmo',
estimator='mean', markers=True, palette='inferno')
plt.title("Tiempo de ejecución promedio vs. n (por algoritmo)\n")
plt.ylabel("Tiempo de ejecución (ns)")
plt.xlabel("Tamaño (n)")
plt.legend()
plt.show()
df_ok_hasta_n14 = df_ok[df_ok['n'] <= 14]
plt.figure(figsize=(6,4))
sns.lineplot(data=df_ok_hasta_n14, x='n', y='tiempo_ejecucion', hue='algoritmo',
estimator='mean', markers=True, palette = 'inferno')
plt.title("Tiempo de ejecución promedio vs. n (por algoritmo)\n")
plt.ylabel("Tiempo de ejecución (ns)")
plt.xlabel("Tamaño (n)")
plt.legend()
plt.show()
plot_tiempo_vs_n(df_ok)
plot_tiempo_vs_n(df_subset, palette="tab10") #tab10, hls, Spectral, husl
Uso de memoria:¶
plt.figure(figsize=(6,4))
sns.lineplot(data=df_ok, x='n', y='memoria_max_mb', hue='algoritmo',
estimator='mean', markers=True, palette = 'tab10')
plt.title("Uso de Memoria (MB) vs. n")
plt.ylabel("Memoria (MB)")
plt.xlabel("Tamaño (n)")
plt.legend()
plt.show()
plt.figure(figsize=(6,4))
sns.lineplot(data=df_subset, x='n', y='memoria_max_mb', hue='algoritmo',
estimator='mean', markers=True, palette = 'tab10')
plt.title("Uso de Memoria (MB) vs. n")
plt.ylabel("Memoria (MB)")
plt.xlabel("Tamaño (n)")
plt.legend()
plt.show()
Gráficos vs crecimientos teóricos¶
# definir la función 2^n hasta 15
def f(n):
return 2**n
x_bruta = np.arange(1, 15)
y_bruta = f(x_bruta)
# definir los n^2
def f2(n):
return n**2
x_n2 = np.arange(1, 400)
y_n2 = f2(x_n2)
e1 = 8e+2
e2 = 6.5e+2
e3 = 17e+1
plt.figure(figsize=(6,4))
sns.lineplot(data=df_ok, x='n', y='tiempo_ejecucion', hue='algoritmo',
estimator='mean', markers=True, palette = 'inferno')
sns.lineplot(x=x_bruta, y=e1*y_bruta, color='green', linestyle=':', label='$2^{n}$ fuerza bruta')
sns.lineplot(x=x_n2, y=e2*y_n2, color='magenta', linestyle=':', label='$n^{2}$ Rec memo')
sns.lineplot(x=x_n2, y=e3*y_n2, color='orangered', linestyle=':', label='$n^{2}$ DP')
plt.title("Tiempo de ejecución promedio vs.\n Tiempos teóricos por algoritmo\n")
plt.ylabel("Tiempo de ejecución (ns)")
plt.xlabel("Tamaño (n)")
plt.legend()
plt.show()
Más estadística descriptiva:¶
def boxplot(data=df_ok, palette='viridis'):
plt.figure(figsize=(10, 5))
sns.boxplot(
data=data,
x='n',
y='tiempo_ejecucion',
hue='algoritmo',
palette=palette,
showfliers=False # Opcional: ocultar outliers si hay muchos
)
plt.yscale('log') # Escala logarítmica para mejor visualización
plt.title("Distribución de Tiempos de Ejecución por Algoritmo y Tamaño n (Escala Logarítmica)\n")
plt.xlabel("Tamaño (n)")
plt.ylabel("Tiempo de Ejecución (ns)")
plt.legend(bbox_to_anchor=(1.05, 1), loc='upper left')
plt.show()
boxplot(df_ok, 'bright')
def grafico_barras_categorias(data=df_ok, palette='viridis'):
"""Barras agrupadas por categoría de tamaño"""
plt.figure(figsize=(10, 6))
sns.barplot(
data=data,
x='category_size',
y='tiempo_ejecucion',
hue='algoritmo',
palette=palette,
estimator='median',
errorbar=None
)
plt.yscale('log')
plt.title("Tiempo Promedio por Categoría de Tamaño")
plt.xlabel("Categoría")
plt.ylabel("Tiempo (ns) - Escala Log")
plt.legend(title='Algoritmo')
plt.show()
grafico_barras_categorias(df_ok, 'magma')
def grafico_facetgrid_tipos(data=df_ok, palette='tab10'):
"""FacetGrid comparando tipos de instancia"""
g = sns.FacetGrid(
data,
col='tipo_instancia',
hue='algoritmo',
palette=palette,
height=4,
aspect=1.2
)
g.map(sns.lineplot, 'n', 'tiempo_ejecucion', estimator='mean', marker='o')
g.add_legend()
g.set_axis_labels("Tamaño (n)", "Tiempo (ns)")
g.set_titles("Tipo de Instancia: {col_name}")
plt.subplots_adjust(top=0.8)
g.fig.suptitle("Comparación entre Tipos de Instancia")
plt.show()
grafico_facetgrid_tipos(df_ok, 'inferno')
def grafico_interactivo_plotly(data=df_ok, palette='viridis'):
"""Gráfico interactivo con Plotly"""
fig = px.line(
data,
x='n',
y='tiempo_ejecucion',
color='algoritmo',
line_group='replica_id',
facet_col='tipo_instancia',
log_y=True,
title="Análisis Interactivo de Tiempos",
labels={'n': 'Tamaño (n)', 'tiempo_ejecucion': 'Tiempo (ns)'},
color_discrete_sequence=sns.color_palette(palette).as_hex()
)
fig.update_layout(height=700, width=1000)
fig.show()
grafico_interactivo_plotly(df_ok, 'plasma')
def scatter_tiempo_vs_memoria(df=None, palette="magma"):
"""
Muestra un diagrama de dispersión (scatterplot) de tiempo_ejecucion vs memoria_max_mb,
coloreado por algoritmo. Útil para ver correlación entre tiempo y memoria.
"""
if df is None:
print("Advertencia: df es None. Usando df_ok por defecto.")
df = df_ok
plt.figure(figsize=(6,4))
sns.scatterplot(
data=df,
x='memoria_max_mb',
y='tiempo_ejecucion',
hue='algoritmo',
palette=palette
)
plt.title("Relación entre Tiempo y Memoria por Algoritmo")
plt.xlabel("Memoria (MB)")
plt.ylabel("Tiempo de ejecución (ns)")
plt.legend()
plt.tight_layout()
plt.show()
scatter_tiempo_vs_memoria(df_ok, 'inferno')
5.2 Contraste de Hipótesis (ANOVA, Pruebas Post-hoc, t-Test, etc.)¶
5.2.1 ANOVA¶
Para la Hipótesis 1 (tiempo de ejecución):
Podemos realizar un ANOVA de un factor (algoritmo) para un n fijo, o un ANOVA de dos factores (algoritmo, n). Ejemplo con statsmodels:
# Filtramos un n mediano, por ejemplo n=14 (donde todos tienen datos)
df_n14 = df_ok[df_ok['n'] == 14]
model = ols('tiempo_ejecucion ~ C(algoritmo)', data=df_n14).fit()
anova_results = sm.stats.anova_lm(model, typ=2)
print(anova_results)
sum_sq df F PR(>F) C(algoritmo) 5.387558e+15 2.0 369.190914 2.896695e-81 Residual 2.167042e+15 297.0 NaN NaN
- Significado del p-valor (ANOVA)
Como el valor $PR(>F) = 2.896695 × 10^{-81}$ es extremadamente pequeño (mucho menor a $0.05$ o incluso $0.001$).
Esto indica que podemos rechazar la hipótesis nula $H_0$ de que "todas las medias de las mediciones (una por cada algoritmo) son iguales" en el tamaño $n=14$.
En otras palabras, al menos un algoritmo difiere significativamente de los demás en la métrica que has analizado (puede que sea el tiempo de ejecución, la versión logarítmica de tiempo, etc.).
model = ols('tiempo_ejecucion ~ C(algoritmo)', data=df_ok_hasta_n14).fit()
anova_results = sm.stats.anova_lm(model, typ=2)
print(anova_results)
sum_sq df F PR(>F) C(algoritmo) 1.258443e+15 2.0 105.050401 2.030166e-43 Residual 8.966597e+15 1497.0 NaN NaN
- Significado del p-valor (ANOVA)
Como el valor $PR(>F) = 2.030166 × 10^{-43}$ es extremadamente pequeño (mucho menor a $0.05$ o incluso $0.001$).
Esto indica que podemos rechazar la hipótesis nula $H_0$ de que "todas las medias de las mediciones (una por cada algoritmo) son iguales" en el tamaño $n\leq 14$.
En otras palabras, al menos un algoritmo difiere significativamente de los demás en la métrica que has analizado (puede que sea el tiempo de ejecución, la versión logarítmica de tiempo, etc.).
# Usamos todos los tamaños n de las instancias
model = ols('tiempo_ejecucion ~ C(algoritmo)', data=df_ok).fit()
anova_results = sm.stats.anova_lm(model, typ=2)
print(anova_results)
sum_sq df F PR(>F) C(algoritmo) 3.520056e+16 2.0 89.383672 6.295298e-39 Residual 1.082398e+18 5497.0 NaN NaN
- Significado del p-valor (ANOVA)
Como el valor $PR(>F) = 6.295298 × 10^{-39}$ es extremadamente más pequeño (mucho menor a $0.05$ o incluso $0.001$).
Esto indica que podemos rechazar la hipótesis nula $H_0$ de que "todas las medias de las mediciones (una por cada algoritmo) son iguales". Sin embargo hay un sesgo en el tamaño de instancias de: fuerza_bruta_rec, entonces solo podemos comparar directamente rec_con_memo con prog_dinamica y si queremos compararlos a su vez con fuerza_bruta_rec, debe ser en el intervalo $n = [1,15].$
En otras palabras, al menos un algoritmo difiere significativamente de los demás en la métrica que has analizado (puede que sea el tiempo de ejecución, la versión logarítmica de tiempo, etc.).
# Usamos todos los tamaños n de las instancias
model = ols('tiempo_ejecucion ~ C(algoritmo)*C(n)', data=df_ok).fit()
anova_results = sm.stats.anova_lm(model, typ=2)
print(anova_results)
sum_sq df F PR(>F) C(algoritmo) 7.405152e+14 2.0 13.345624 0.000002 C(n) 1.150145e+15 24.0 1.727333 0.015118 C(algoritmo):C(n) 9.068080e+09 48.0 0.000007 0.997918 Residual 1.510647e+17 5445.0 NaN NaN
/usr/local/lib/python3.11/dist-packages/statsmodels/base/model.py:1894: ValueWarning: covariance of constraints does not have full rank. The number of constraints is 48, but rank is 1
Aquí de hecho python nos hace la recomendación de que esto no se debería hacer: ValueWarning: covariance of constraints does not have full rank. The number of constraints is 48, but rank is 1 warnings.warn('covariance of constraints does not have full '
Dado que al agregar $*C(n)$ en el model ols estamos viendo sí hay diferencias entre las instancias y los algoritmos y aunque es cierto hay una infraproporción de uno de los algorimtos, en este caso: fuerza_bruta_rec. Ya ahondaremos más en las pruebas Tukey y veremos el sesgo a profundidad...
- Conclusión General del ANOVA
Existe un efecto significativo del factor "algoritmo" sobre la variable dependiente (la que estés midiendo). No se sabe todavía cuáles algoritmos difieren entre sí; para eso se hace el análisis post-hoc (Tukey u otro).
5.2.2 Pruebas post-hoc¶
Luego, hacemos pruebas post-hoc (p.ej., TukeyHSD):
# Prubea de los tres algoritmos en n = 14
mc1 = pairwise_tukeyhsd(df_n14['tiempo_ejecucion'], df_n14['algoritmo'], alpha=0.05)
print(mc1)
Multiple Comparison of Means - Tukey HSD, FWER=0.05
====================================================================================
group1 group2 meandiff p-adj lower upper reject
------------------------------------------------------------------------------------
fuerza_bruta_rec prog_dinamica -9014641.54 0.0 -9914466.7545 -8114816.3255 True
fuerza_bruta_rec rec_con_memo -8964399.26 0.0 -9864224.4745 -8064574.0455 True
prog_dinamica rec_con_memo 50242.28 0.9905 -849582.9345 950067.4945 False
------------------------------------------------------------------------------------
Esto nos indica qué pares de algoritmos difieren significativamente con $n = 14$ y es obtiene:
fuerza_bruta_recconrec_con_memo: $P$-valor $\approx 0$ y se rechaza (reject =True).fuerza_bruta_recconprog_dinamica: $P$-valor $\approx 0$ y se rechaza (reject =True).rec_con_memoconprog_dinamica$P$-valor $= 0.9905$ y NO se rechaza (reject =False). Es decir con n = 14 no hay suficiente evidencia estadística, para decir que los dos algoritmos difieren en tiempo.
# Prubea de los tres algoritmos en n < 15
mc2 = pairwise_tukeyhsd(df_ok_hasta_n14['tiempo_ejecucion'], df_ok_hasta_n14['algoritmo'], alpha=0.05)
print(mc2)
Multiple Comparison of Means - Tukey HSD, FWER=0.05
=====================================================================================
group1 group2 meandiff p-adj lower upper reject
-------------------------------------------------------------------------------------
fuerza_bruta_rec prog_dinamica -1959235.566 0.0 -2322370.5323 -1596100.5997 True
fuerza_bruta_rec rec_con_memo -1926389.202 0.0 -2289524.1683 -1563254.2357 True
prog_dinamica rec_con_memo 32846.364 0.9755 -330288.6023 395981.3303 False
-------------------------------------------------------------------------------------
Aquí observamos un resultado similar a la varianza tomada en $n = 14$ y ahora con $n \leq 14$ se obtiene:
fuerza_bruta_recconrec_con_memo: $P$-valor $\approx 0$ y se rechaza (reject =True).fuerza_bruta_recconprog_dinamica: $P$-valor $\approx 0$ y se rechaza (reject =True).rec_con_memoconprog_dinamica$P$-valor $= 0.9755$ y NO se rechaza (reject =False). Es decir con $n \leq 14$ no hay suficiente evidencia estadística, para decir que los dos algoritmos difieren en tiempo.
# Ahora veamos rec_con_memo con prog_dinamica en todos los n, es decir entre 1 y 400
df_xl = df_subset[df_subset['algoritmo'].isin(['rec_con_memo', 'prog_dinamica'])]
mc3 = pairwise_tukeyhsd(df_xl['tiempo_ejecucion'], df_xl['algoritmo'], alpha=0.05)
print(mc3)
Multiple Comparison of Means - Tukey HSD, FWER=0.05
==============================================================================
group1 group2 meandiff p-adj lower upper reject
------------------------------------------------------------------------------
prog_dinamica rec_con_memo 5057204.1656 0.0 4244535.1716 5869873.1596 True
------------------------------------------------------------------------------
Aquí observamos que rec_con_memo con prog_dinamica $P$-valor $\approx 0$ y se rechaza (reject = True).
Es decir con todos los $n$ hay suficiente evidencia estadística, para decir que los $2$ algoritmos difieren en tiempo.
# Ahora hagamos la prueba con TODOS los n en los 3 algoritmos, para ver el sesgo entre
# Fuerza bruta y prgramación dinámica:
mc4 = pairwise_tukeyhsd(df_ok['tiempo_ejecucion'], df_ok['algoritmo'], alpha=0.05)
print(mc4)
Multiple Comparison of Means - Tukey HSD, FWER=0.05
====================================================================================
group1 group2 meandiff p-adj lower upper reject
------------------------------------------------------------------------------------
fuerza_bruta_rec prog_dinamica 137689.9644 0.9781 -1473906.5603 1749286.4891 False
fuerza_bruta_rec rec_con_memo 5194894.13 0.0 3583297.6053 6806490.6547 True
prog_dinamica rec_con_memo 5057204.1656 0.0 4126748.4783 5987659.8529 True
------------------------------------------------------------------------------------
Esto nos indica qué pares de algoritmos difieren significativamente con todos los $n$ y se obtiene:
fuerza_bruta_recconprog_dinamica: $P$-valor $= 0.9781 $ y NO se rechaza (reject =False). Sin embargo esto sucede porque NO se deberían comparar los experimentos de los dos algorimtos debido a la diferencia abismal de las varianzas entre las medidas de los tiempos, ya que los $n$ en que se evalúan son demasiado dispajeros hay 2000 experimentos menos enfuerza_bruta_rec. Por lo tanto ese p-valor está sesgado estadísticamente hablando.fuerza_bruta_recconrec_con_memo: $P$-valor $\approx 0$ y se rechaza (reject =True).rec_con_memoconprog_dinamica$P$-valor $\approx 0$ y se rechaza (reject =True).
Es decir con todos los $n$ hay suficiente evidencia estadística, para decir que TODOS los algoritmos difieren en tiempo.
5.2.3 Prueba t-Test¶
Para comparar “Recursivo con Memo” vs. “Prog Dinámica” en términos de memoria, por ejemplo, podríamos filtrar esos dos algoritmos y realizar un t-test:
df_rmemo = df_ok[df_ok['algoritmo'] == 'rec_con_memo']
df_pdin = df_ok[df_ok['algoritmo'] == 'prog_dinamica']
stat, pval = ttest_ind(df_rmemo['memoria_max_mb'], df_pdin['memoria_max_mb'], equal_var=False)
print(f"T-test Memoria Rec Memo vs Prog Din:\n\n ● statistic = {stat}\n ● P-value = {pval}")
T-test Memoria Rec Memo vs Prog Din: ● statistic = 2.248913319566825 ● P-value = 0.02460477898059686
Si $p<0.05$, rechazamos la hipótesis nula de igualdad de medias en la meoria máxima almacenada en cada algoritmo (Recursivo memo y programación dinámica)
Interpretación del p-value
El $p$-valor $= 0.0246047$ es mucho menor que cualquier umbral típico de significancia (por ejemplo, $α = 0.05$).
Esto implica que se rechaza la hipótesis nula de igualdad de medias.
En otras palabras, hay evidencia estadística suficiente para afirmar que Recursivo con Memo y Programación Dinámica difieren en promedio en su uso de memoria (al menos bajo los datos, supuestos y tamaño de muestra con que se corrió la prueba).
Conclusión
Dado un $p$-value = $= 0.0246047$ (< $0.05$),se puede concluir que existe una diferencia significativa entre el uso de memoria de
"Rec. con Memo"y"Prog. Dinámica". Dicho en palabras castizas:"Se detectan diferencias estadísticamente significativas entre la memoria consumida por el algoritmo recursivo con memoización y la programación dinámica, con el nivel de significancia del $5\%$"
5.3 Estadística Descriptiva usando tracemalloc¶
# El archivo "resultados_optimizados.csv" es el más grande usado convertido
# del json de 80 MB con 50 réplicas en todos los tamaño y cargamos el usó:
# tracemalloc, para medir memoria, sin embargo veamos las diferencias:
df2 = pd.read_csv("resultados_optimizados2.csv")
df2.head() # primeras 5 filas del dataset
| language | category_size | n | tipo_instancia | algoritmo | replica_id | tiempo_ejecucion | memoria_max_mb | costo_minimo | status | |
|---|---|---|---|---|---|---|---|---|---|---|
| 0 | Python | XS | 4 | uniforme | fuerza_bruta_rec | 0 | 693276.0 | 0.000214 | 8.0 | ok |
| 1 | Python | XS | 4 | uniforme | rec_con_memo | 0 | 392730.0 | 0.000359 | 8.0 | ok |
| 2 | Python | XS | 4 | uniforme | prog_dinamica | 0 | 234636.0 | 0.000206 | 8.0 | ok |
| 3 | Python | XS | 4 | uniforme | fuerza_bruta_rec | 1 | 284901.0 | 0.000214 | 5.0 | ok |
| 4 | Python | XS | 4 | uniforme | rec_con_memo | 1 | 266267.0 | 0.000359 | 5.0 | ok |
df2['status'].value_counts() # cuántos experimentos no pasaron por ser fuerza_bruta_recursiva
| count | |
|---|---|
| status | |
| ok | 5500 |
| skipped_due_to_large_n | 2000 |
df2['memoria_max_mb'].value_counts() # contar los valores almacenados en la memoria
| count | |
|---|---|
| memoria_max_mb | |
| 0.000359 | 207 |
| 0.000214 | 200 |
| 0.000252 | 130 |
| 0.000519 | 102 |
| 0.001320 | 101 |
| ... | ... |
| 0.001747 | 1 |
| 0.001213 | 1 |
| 0.002815 | 1 |
| 0.002014 | 1 |
| 0.000946 | 1 |
69 rows × 1 columns
df2.info() # Información de los valores nulos
<class 'pandas.core.frame.DataFrame'> RangeIndex: 7500 entries, 0 to 7499 Data columns (total 10 columns): # Column Non-Null Count Dtype --- ------ -------------- ----- 0 language 7500 non-null object 1 category_size 7500 non-null object 2 n 7500 non-null int64 3 tipo_instancia 7500 non-null object 4 algoritmo 7500 non-null object 5 replica_id 7500 non-null int64 6 tiempo_ejecucion 5500 non-null float64 7 memoria_max_mb 5500 non-null float64 8 costo_minimo 5500 non-null float64 9 status 7500 non-null object dtypes: float64(3), int64(2), object(5) memory usage: 586.1+ KB
# Filtrar filas skip para quedarse solo con los valores no null
df2_ok = df2[df2['status'] == 'ok']
df2_ok.head()
| language | category_size | n | tipo_instancia | algoritmo | replica_id | tiempo_ejecucion | memoria_max_mb | costo_minimo | status | |
|---|---|---|---|---|---|---|---|---|---|---|
| 0 | Python | XS | 4 | uniforme | fuerza_bruta_rec | 0 | 693276.0 | 0.000214 | 8.0 | ok |
| 1 | Python | XS | 4 | uniforme | rec_con_memo | 0 | 392730.0 | 0.000359 | 8.0 | ok |
| 2 | Python | XS | 4 | uniforme | prog_dinamica | 0 | 234636.0 | 0.000206 | 8.0 | ok |
| 3 | Python | XS | 4 | uniforme | fuerza_bruta_rec | 1 | 284901.0 | 0.000214 | 5.0 | ok |
| 4 | Python | XS | 4 | uniforme | rec_con_memo | 1 | 266267.0 | 0.000359 | 5.0 | ok |
df2_ok.info() # Corroborar valores no null
<class 'pandas.core.frame.DataFrame'> Index: 5500 entries, 0 to 7499 Data columns (total 10 columns): # Column Non-Null Count Dtype --- ------ -------------- ----- 0 language 5500 non-null object 1 category_size 5500 non-null object 2 n 5500 non-null int64 3 tipo_instancia 5500 non-null object 4 algoritmo 5500 non-null object 5 replica_id 5500 non-null int64 6 tiempo_ejecucion 5500 non-null float64 7 memoria_max_mb 5500 non-null float64 8 costo_minimo 5500 non-null float64 9 status 5500 non-null object dtypes: float64(3), int64(2), object(5) memory usage: 472.7+ KB
# 1) Descripción general en TIEMPO
desc_tiempos2 = df2_ok.groupby(['n','algoritmo'])['tiempo_ejecucion'].describe()
print(desc_tiempos2)
count mean std min \
n algoritmo
4 fuerza_bruta_rec 100.0 3.672911e+04 2.120665e+04 19579.0
prog_dinamica 100.0 3.717457e+04 1.113716e+04 23245.0
rec_con_memo 100.0 4.082959e+04 1.143614e+04 20744.0
5 fuerza_bruta_rec 100.0 8.236321e+04 3.103806e+05 35216.0
prog_dinamica 100.0 5.254474e+04 1.271935e+05 25378.0
rec_con_memo 100.0 1.298036e+05 6.702027e+05 30012.0
7 fuerza_bruta_rec 100.0 1.506144e+05 2.054311e+04 116730.0
prog_dinamica 100.0 4.509742e+04 1.636492e+04 31451.0
rec_con_memo 100.0 5.856351e+04 7.940189e+03 39281.0
10 fuerza_bruta_rec 100.0 1.148520e+06 3.594599e+05 926737.0
prog_dinamica 100.0 5.843086e+04 7.575043e+03 47492.0
rec_con_memo 100.0 8.211965e+04 1.308444e+04 60290.0
14 fuerza_bruta_rec 100.0 1.769650e+07 2.158101e+06 16427861.0
prog_dinamica 100.0 8.438599e+04 6.619772e+03 69105.0
rec_con_memo 100.0 1.332124e+05 1.924807e+04 105308.0
15 prog_dinamica 100.0 9.024565e+04 1.766534e+04 78404.0
rec_con_memo 100.0 1.189243e+05 1.083920e+04 93793.0
18 prog_dinamica 100.0 1.092477e+05 1.724999e+04 95914.0
rec_con_memo 100.0 1.470155e+05 1.243464e+04 128960.0
20 prog_dinamica 100.0 1.224147e+05 1.136741e+04 89483.0
rec_con_memo 100.0 1.708389e+05 3.115107e+04 146110.0
22 prog_dinamica 100.0 1.355932e+05 8.540056e+03 121348.0
rec_con_memo 100.0 1.874461e+05 1.743643e+04 149147.0
24 prog_dinamica 100.0 1.526684e+05 1.146654e+04 140693.0
rec_con_memo 100.0 2.111226e+05 2.304676e+04 180997.0
25 prog_dinamica 100.0 1.586851e+05 1.606765e+04 125010.0
rec_con_memo 100.0 2.056264e+05 3.266656e+04 169094.0
30 prog_dinamica 100.0 1.976547e+05 1.666765e+04 160700.0
rec_con_memo 100.0 3.760805e+05 6.533605e+05 231628.0
35 prog_dinamica 100.0 2.417241e+05 2.151446e+04 217485.0
rec_con_memo 100.0 3.583913e+05 2.939228e+04 317347.0
40 prog_dinamica 100.0 2.826876e+05 1.596455e+04 249952.0
rec_con_memo 100.0 4.057497e+05 2.721344e+04 355352.0
45 prog_dinamica 100.0 3.395203e+05 2.572842e+04 294460.0
rec_con_memo 100.0 5.485518e+05 1.799504e+05 471947.0
50 prog_dinamica 100.0 3.936965e+05 5.001033e+04 339985.0
rec_con_memo 100.0 6.169000e+05 2.411156e+05 503667.0
60 prog_dinamica 100.0 5.241085e+05 1.772389e+05 458012.0
rec_con_memo 100.0 9.590492e+05 3.949873e+05 809225.0
70 prog_dinamica 100.0 6.715364e+05 2.626546e+05 549537.0
rec_con_memo 100.0 1.383319e+06 7.219193e+05 1138921.0
80 prog_dinamica 100.0 8.526398e+05 4.269023e+05 711649.0
rec_con_memo 100.0 1.969988e+06 9.034087e+05 1558344.0
90 prog_dinamica 100.0 1.242631e+06 1.350484e+06 859622.0
rec_con_memo 100.0 2.571467e+06 1.430751e+06 2033515.0
100 prog_dinamica 100.0 1.082347e+06 3.891962e+04 965947.0
rec_con_memo 100.0 2.641339e+06 3.817436e+05 2336097.0
120 prog_dinamica 100.0 1.460519e+06 1.202568e+05 1355543.0
rec_con_memo 100.0 3.614606e+06 1.504725e+05 3329525.0
150 prog_dinamica 100.0 2.950594e+06 2.424416e+06 1924454.0
rec_con_memo 100.0 8.187272e+06 3.744949e+06 5250770.0
200 prog_dinamica 100.0 6.106679e+06 3.783294e+06 3095022.0
rec_con_memo 100.0 1.644409e+07 7.180749e+06 9654442.0
400 prog_dinamica 100.0 1.730509e+08 8.943885e+07 61511408.0
rec_con_memo 100.0 3.747097e+08 1.729599e+08 147055481.0
25% 50% 75% max
n algoritmo
4 fuerza_bruta_rec 2.947025e+04 30517.0 3.704225e+04 175175.0
prog_dinamica 3.345625e+04 34576.5 3.685425e+04 111264.0
rec_con_memo 3.196225e+04 40285.0 4.475675e+04 86960.0
5 fuerza_bruta_rec 4.553400e+04 47609.5 5.459550e+04 3153310.0
prog_dinamica 3.117400e+04 37521.0 4.118325e+04 1300453.0
rec_con_memo 4.047000e+04 45018.0 4.853250e+04 6607098.0
7 fuerza_bruta_rec 1.410185e+05 146981.0 1.565612e+05 293866.0
prog_dinamica 3.951500e+04 40798.0 4.785425e+04 185158.0
rec_con_memo 5.429625e+04 57298.0 6.216500e+04 84040.0
10 fuerza_bruta_rec 1.064648e+06 1075833.0 1.099702e+06 3645519.0
prog_dinamica 5.598725e+04 56981.5 5.790550e+04 112700.0
rec_con_memo 7.710100e+04 79317.5 8.661300e+04 174028.0
14 fuerza_bruta_rec 1.701074e+07 17135093.5 1.745112e+07 32736443.0
prog_dinamica 8.102375e+04 82094.5 8.552700e+04 129975.0
rec_con_memo 1.209040e+05 129130.5 1.410998e+05 211069.0
15 prog_dinamica 8.477850e+04 85600.0 8.881375e+04 233386.0
rec_con_memo 1.125822e+05 117756.0 1.244415e+05 149348.0
18 prog_dinamica 1.037500e+05 104737.0 1.106018e+05 257207.0
rec_con_memo 1.401650e+05 143668.5 1.528768e+05 230719.0
20 prog_dinamica 1.170760e+05 118451.5 1.253740e+05 166568.0
rec_con_memo 1.584570e+05 164757.0 1.728425e+05 391035.0
22 prog_dinamica 1.310965e+05 132343.5 1.396422e+05 173430.0
rec_con_memo 1.791205e+05 185819.5 1.924405e+05 298748.0
24 prog_dinamica 1.458162e+05 147103.5 1.577512e+05 209415.0
rec_con_memo 1.988742e+05 207513.5 2.145770e+05 345448.0
25 prog_dinamica 1.505238e+05 155387.5 1.644402e+05 263514.0
rec_con_memo 1.922615e+05 200279.5 2.091140e+05 474843.0
30 prog_dinamica 1.898485e+05 192994.0 2.014632e+05 310673.0
rec_con_memo 2.549755e+05 282372.5 2.988870e+05 5427028.0
35 prog_dinamica 2.315275e+05 236745.5 2.455768e+05 350723.0
rec_con_memo 3.363832e+05 356051.5 3.734735e+05 465412.0
40 prog_dinamica 2.734710e+05 281214.0 2.882422e+05 354901.0
rec_con_memo 3.949392e+05 401703.5 4.094685e+05 594842.0
45 prog_dinamica 3.273925e+05 336116.5 3.434048e+05 484192.0
rec_con_memo 5.153975e+05 524939.5 5.424295e+05 2304175.0
50 prog_dinamica 3.798090e+05 384523.5 3.914088e+05 814279.0
rec_con_memo 5.701598e+05 580425.0 6.169790e+05 2964041.0
60 prog_dinamica 4.904230e+05 502099.0 5.139478e+05 2255478.0
rec_con_memo 8.792430e+05 900108.5 9.349572e+05 4663551.0
70 prog_dinamica 6.123922e+05 625462.0 6.432558e+05 2506247.0
rec_con_memo 1.243208e+06 1265614.0 1.307121e+06 6405015.0
80 prog_dinamica 7.517260e+05 763020.5 7.821658e+05 3876504.0
rec_con_memo 1.655569e+06 1686565.0 1.757729e+06 6827680.0
90 prog_dinamica 9.075702e+05 916527.5 9.350425e+05 7979248.0
rec_con_memo 2.117959e+06 2146267.5 2.222834e+06 9427040.0
100 prog_dinamica 1.058985e+06 1081864.5 1.097238e+06 1212146.0
rec_con_memo 2.521265e+06 2562489.5 2.630959e+06 5541984.0
120 prog_dinamica 1.410779e+06 1436889.0 1.465231e+06 2446152.0
rec_con_memo 3.535964e+06 3587753.5 3.641353e+06 4461993.0
150 prog_dinamica 2.092257e+06 2129970.0 2.313710e+06 19191259.0
rec_con_memo 5.648558e+06 5777588.5 1.059332e+07 20320123.0
200 prog_dinamica 3.452079e+06 3608632.5 8.487574e+06 18674089.0
rec_con_memo 1.033469e+07 13149656.0 2.163816e+07 34478442.0
400 prog_dinamica 1.091877e+08 128164992.0 2.244060e+08 464731393.0
rec_con_memo 2.468323e+08 276588776.0 4.618460e+08 954458005.0
# 1.1) Descripción más específica en TIEMPO
desc_tiempos_especificos2 = df2_ok.groupby(['category_size','algoritmo', 'tipo_instancia'])['tiempo_ejecucion'].describe()
print(desc_tiempos_especificos2)
count mean \
category_size algoritmo tipo_instancia
L prog_dinamica estructurada 250.0 7.697207e+05
uniforme 250.0 7.041240e+05
rec_con_memo estructurada 250.0 1.521234e+06
uniforme 250.0 1.479055e+06
M prog_dinamica estructurada 250.0 2.444284e+05
uniforme 250.0 2.436803e+05
rec_con_memo estructurada 250.0 3.968647e+05
uniforme 250.0 3.608951e+05
S prog_dinamica estructurada 250.0 1.221438e+05
uniforme 250.0 1.219240e+05
rec_con_memo estructurada 250.0 1.656003e+05
uniforme 250.0 1.685387e+05
XL prog_dinamica estructurada 250.0 3.309286e+07
uniforme 250.0 4.076757e+07
rec_con_memo estructurada 250.0 7.334237e+07
uniforme 250.0 8.889641e+07
XS fuerza_bruta_rec estructurada 250.0 3.797827e+06
uniforme 250.0 3.848063e+06
prog_dinamica estructurada 250.0 5.242056e+04
uniforme 250.0 5.863287e+04
rec_con_memo estructurada 250.0 7.634734e+04
uniforme 250.0 1.014641e+05
std min \
category_size algoritmo tipo_instancia
L prog_dinamica estructurada 8.720940e+05 339985.0
uniforme 5.010922e+05 344402.0
rec_con_memo estructurada 1.161664e+06 503667.0
uniforme 1.032636e+06 549940.0
M prog_dinamica estructurada 6.551429e+04 126811.0
uniforme 6.724938e+04 125010.0
rec_con_memo estructurada 4.221863e+05 177615.0
uniforme 1.698466e+05 169094.0
S prog_dinamica estructurada 2.637412e+04 78404.0
uniforme 2.452918e+04 82527.0
rec_con_memo estructurada 3.729910e+04 93793.0
uniforme 3.840276e+04 104810.0
XL prog_dinamica estructurada 7.148272e+07 976357.0
uniforme 8.577326e+07 965947.0
rec_con_memo estructurada 1.499620e+08 2336097.0
uniforme 1.806338e+08 2428502.0
XS fuerza_bruta_rec estructurada 6.930286e+06 21101.0
uniforme 7.132745e+06 19579.0
prog_dinamica estructurada 2.181978e+04 24002.0
uniforme 8.156735e+04 23245.0
rec_con_memo estructurada 9.418435e+04 23068.0
uniforme 4.152926e+05 20744.0
25% 50% \
category_size algoritmo tipo_instancia
L prog_dinamica estructurada 494392.25 628031.5
uniforme 490736.00 626106.0
rec_con_memo estructurada 876876.00 1256247.5
uniforme 884062.75 1292126.0
M prog_dinamica estructurada 191845.25 239479.0
uniforme 188317.00 236251.0
rec_con_memo estructurada 289963.75 354826.5
uniforme 250009.50 362271.0
S prog_dinamica estructurada 103664.75 119198.0
uniforme 103921.75 118401.5
rec_con_memo estructurada 140471.75 165223.5
uniforme 141364.25 165373.5
XL prog_dinamica estructurada 1406451.75 2219875.5
uniforme 1418807.50 2106961.5
rec_con_memo estructurada 3556553.75 10285327.0
uniforme 3530098.50 5676643.0
XS fuerza_bruta_rec estructurada 46287.25 144410.5
uniforme 46738.25 149974.0
prog_dinamica estructurada 35050.75 45795.0
uniforme 38866.75 49265.0
rec_con_memo estructurada 43842.75 58214.5
uniforme 45606.50 60804.5
75% max
category_size algoritmo tipo_instancia
L prog_dinamica estructurada 807284.50 7979248.0
uniforme 771291.75 5315034.0
rec_con_memo estructurada 1873447.25 9427040.0
uniforme 1746115.50 9162728.0
M prog_dinamica estructurada 289375.75 463012.0
uniforme 290547.25 484192.0
rec_con_memo estructurada 413059.00 5427028.0
uniforme 415708.00 2304175.0
S prog_dinamica estructurada 140985.50 257207.0
uniforme 143016.50 233386.0
rec_con_memo estructurada 192487.75 345448.0
uniforme 192043.50 391035.0
XL prog_dinamica estructurada 11426357.75 451821256.0
uniforme 3875220.75 464731393.0
rec_con_memo estructurada 26846731.00 954458005.0
uniforme 12270567.25 947471571.0
XS fuerza_bruta_rec estructurada 1104656.75 21254607.0
uniforme 1086490.00 32736443.0
prog_dinamica estructurada 59365.25 173552.0
uniforme 64778.50 1300453.0
rec_con_memo estructurada 87079.25 1453383.0
uniforme 88348.00 6607098.0
# 1.3) Descripción más específica en TIEMPO
desc_tiempos_especificos3 = df2_ok.groupby(['category_size','tipo_instancia'])['tiempo_ejecucion'].describe()
print(desc_tiempos_especificos3)
count mean std min \
category_size tipo_instancia
L estructurada 500.0 1.145477e+06 1.092871e+06 339985.0
uniforme 500.0 1.091589e+06 8.987910e+05 344402.0
M estructurada 500.0 3.206466e+05 3.112951e+05 126811.0
uniforme 500.0 3.022877e+05 1.417514e+05 125010.0
S estructurada 500.0 1.438721e+05 3.891505e+04 78404.0
uniforme 500.0 1.452313e+05 3.975507e+04 82527.0
XL estructurada 500.0 5.321761e+07 1.190687e+08 976357.0
uniforme 500.0 6.483199e+07 1.432934e+08 965947.0
XS estructurada 750.0 1.308865e+06 4.367113e+06 21101.0
uniforme 750.0 1.336053e+06 4.486932e+06 19579.0
25% 50% 75% max
category_size tipo_instancia
L estructurada 574278.25 864682.5 1269328.25 9427040.0
uniforme 606793.50 868648.0 1307121.00 9162728.0
M estructurada 207856.75 289768.5 360694.00 5427028.0
uniforme 206218.50 273437.5 368689.25 2304175.0
S estructurada 116503.75 140720.0 168073.75 345448.0
uniforme 116676.00 141527.0 167991.50 391035.0
XL estructurada 2238943.25 3754871.0 21164852.50 954458005.0
uniforme 2107432.25 3557612.5 10620444.25 947471571.0
XS estructurada 39881.75 56700.0 121830.25 21254607.0
uniforme 42440.25 58523.5 128932.50 32736443.0
# 2) Descripción general en ESPACIO
desc_espacio2 = df2_ok.groupby(['n','algoritmo'])['memoria_max_mb'].describe()
print(desc_espacio2)
count mean std min 25% \
n algoritmo
4 fuerza_bruta_rec 100.0 0.000214 0.000000e+00 0.000214 0.000214
prog_dinamica 100.0 0.000206 1.906912e-19 0.000206 0.000206
rec_con_memo 100.0 0.000290 3.156791e-05 0.000252 0.000252
5 fuerza_bruta_rec 100.0 0.000259 0.000000e+00 0.000259 0.000259
prog_dinamica 100.0 0.000214 0.000000e+00 0.000214 0.000214
rec_con_memo 100.0 0.000361 1.051807e-05 0.000359 0.000359
7 fuerza_bruta_rec 100.0 0.000351 0.000000e+00 0.000351 0.000351
prog_dinamica 100.0 0.000229 0.000000e+00 0.000229 0.000229
rec_con_memo 100.0 0.000466 7.514473e-06 0.000465 0.000465
10 fuerza_bruta_rec 100.0 0.000488 0.000000e+00 0.000488 0.000488
prog_dinamica 100.0 0.000252 3.813825e-19 0.000252 0.000252
rec_con_memo 100.0 0.000627 7.514473e-06 0.000626 0.000626
14 fuerza_bruta_rec 100.0 0.000671 0.000000e+00 0.000671 0.000671
prog_dinamica 100.0 0.000282 4.903489e-19 0.000282 0.000282
rec_con_memo 100.0 0.000840 5.340576e-06 0.000839 0.000839
15 prog_dinamica 100.0 0.000290 0.000000e+00 0.000290 0.000290
rec_con_memo 100.0 0.000893 5.340576e-06 0.000893 0.000893
18 prog_dinamica 100.0 0.000313 5.993153e-19 0.000313 0.000313
rec_con_memo 100.0 0.001053 5.340576e-06 0.001053 0.001053
20 prog_dinamica 100.0 0.000328 6.537985e-19 0.000328 0.000328
rec_con_memo 100.0 0.001160 5.340576e-06 0.001160 0.001160
22 prog_dinamica 100.0 0.000343 6.537985e-19 0.000343 0.000343
rec_con_memo 100.0 0.001267 5.340576e-06 0.001266 0.001266
24 prog_dinamica 100.0 0.000359 7.082817e-19 0.000359 0.000359
rec_con_memo 100.0 0.001373 0.000000e+00 0.001373 0.001373
25 prog_dinamica 100.0 0.000366 0.000000e+00 0.000366 0.000366
rec_con_memo 100.0 0.001427 5.340576e-06 0.001427 0.001427
30 prog_dinamica 100.0 0.000404 7.627649e-19 0.000404 0.000404
rec_con_memo 100.0 0.001694 5.340576e-06 0.001694 0.001694
35 prog_dinamica 100.0 0.000443 0.000000e+00 0.000443 0.000443
rec_con_memo 100.0 0.001961 5.340576e-06 0.001961 0.001961
40 prog_dinamica 100.0 0.000481 8.717313e-19 0.000481 0.000481
rec_con_memo 100.0 0.002228 0.000000e+00 0.002228 0.002228
45 prog_dinamica 100.0 0.000519 0.000000e+00 0.000519 0.000519
rec_con_memo 100.0 0.002495 5.340576e-06 0.002495 0.002495
50 prog_dinamica 100.0 0.000557 9.806978e-19 0.000557 0.000557
rec_con_memo 100.0 0.002762 5.340576e-06 0.002762 0.002762
60 prog_dinamica 100.0 0.000633 8.717313e-19 0.000633 0.000633
rec_con_memo 100.0 0.003296 5.340576e-06 0.003296 0.003296
70 prog_dinamica 100.0 0.000710 1.089664e-19 0.000710 0.000710
rec_con_memo 100.0 0.003830 5.340576e-06 0.003830 0.003830
80 prog_dinamica 100.0 0.000786 4.358657e-19 0.000786 0.000786
rec_con_memo 100.0 0.004364 0.000000e+00 0.004364 0.004364
90 prog_dinamica 100.0 0.000862 7.627649e-19 0.000862 0.000862
rec_con_memo 100.0 0.004899 5.340576e-06 0.004898 0.004898
100 prog_dinamica 100.0 0.000938 1.198631e-18 0.000938 0.000938
rec_con_memo 100.0 0.005433 5.340576e-06 0.005432 0.005432
120 prog_dinamica 100.0 0.001091 1.743463e-18 0.001091 0.001091
rec_con_memo 100.0 0.006501 5.340576e-06 0.006500 0.006500
150 prog_dinamica 100.0 0.001320 2.397261e-18 0.001320 0.001320
rec_con_memo 100.0 0.008102 0.000000e+00 0.008102 0.008102
200 prog_dinamica 100.0 0.001701 2.833127e-18 0.001701 0.001701
rec_con_memo 100.0 0.010778 1.610244e-05 0.010773 0.010773
400 prog_dinamica 100.0 0.003349 3.922791e-18 0.003349 0.003349
rec_con_memo 100.0 0.025884 1.610244e-05 0.025879 0.025879
50% 75% max
n algoritmo
4 fuerza_bruta_rec 0.000214 0.000214 0.000214
prog_dinamica 0.000206 0.000206 0.000206
rec_con_memo 0.000305 0.000305 0.000359
5 fuerza_bruta_rec 0.000259 0.000259 0.000259
prog_dinamica 0.000214 0.000214 0.000214
rec_con_memo 0.000359 0.000359 0.000412
7 fuerza_bruta_rec 0.000351 0.000351 0.000351
prog_dinamica 0.000229 0.000229 0.000229
rec_con_memo 0.000465 0.000465 0.000519
10 fuerza_bruta_rec 0.000488 0.000488 0.000488
prog_dinamica 0.000252 0.000252 0.000252
rec_con_memo 0.000626 0.000626 0.000679
14 fuerza_bruta_rec 0.000671 0.000671 0.000671
prog_dinamica 0.000282 0.000282 0.000282
rec_con_memo 0.000839 0.000839 0.000893
15 prog_dinamica 0.000290 0.000290 0.000290
rec_con_memo 0.000893 0.000893 0.000946
18 prog_dinamica 0.000313 0.000313 0.000313
rec_con_memo 0.001053 0.001053 0.001106
20 prog_dinamica 0.000328 0.000328 0.000328
rec_con_memo 0.001160 0.001160 0.001213
22 prog_dinamica 0.000343 0.000343 0.000343
rec_con_memo 0.001266 0.001266 0.001320
24 prog_dinamica 0.000359 0.000359 0.000359
rec_con_memo 0.001373 0.001373 0.001373
25 prog_dinamica 0.000366 0.000366 0.000366
rec_con_memo 0.001427 0.001427 0.001480
30 prog_dinamica 0.000404 0.000404 0.000404
rec_con_memo 0.001694 0.001694 0.001747
35 prog_dinamica 0.000443 0.000443 0.000443
rec_con_memo 0.001961 0.001961 0.002014
40 prog_dinamica 0.000481 0.000481 0.000481
rec_con_memo 0.002228 0.002228 0.002228
45 prog_dinamica 0.000519 0.000519 0.000519
rec_con_memo 0.002495 0.002495 0.002548
50 prog_dinamica 0.000557 0.000557 0.000557
rec_con_memo 0.002762 0.002762 0.002815
60 prog_dinamica 0.000633 0.000633 0.000633
rec_con_memo 0.003296 0.003296 0.003349
70 prog_dinamica 0.000710 0.000710 0.000710
rec_con_memo 0.003830 0.003830 0.003883
80 prog_dinamica 0.000786 0.000786 0.000786
rec_con_memo 0.004364 0.004364 0.004364
90 prog_dinamica 0.000862 0.000862 0.000862
rec_con_memo 0.004898 0.004898 0.004951
100 prog_dinamica 0.000938 0.000938 0.000938
rec_con_memo 0.005432 0.005432 0.005486
120 prog_dinamica 0.001091 0.001091 0.001091
rec_con_memo 0.006500 0.006500 0.006554
150 prog_dinamica 0.001320 0.001320 0.001320
rec_con_memo 0.008102 0.008102 0.008102
200 prog_dinamica 0.001701 0.001701 0.001701
rec_con_memo 0.010773 0.010773 0.010826
400 prog_dinamica 0.003349 0.003349 0.003349
rec_con_memo 0.025879 0.025879 0.025932
# 2.1) Descripción más específica en ESPACIO
desc_tiempos_especificos2 = df2_ok.groupby(['category_size', 'tipo_instancia'])['memoria_max_mb'].describe()
print(desc_tiempos_especificos2)
count mean std min 25% \
category_size tipo_instancia
L estructurada 500.0 0.002270 0.001653 0.000557 0.000710
uniforme 500.0 0.002270 0.001653 0.000557 0.000710
M estructurada 500.0 0.001202 0.000807 0.000366 0.000443
uniforme 500.0 0.001202 0.000807 0.000366 0.000443
S estructurada 500.0 0.000738 0.000429 0.000290 0.000328
uniforme 500.0 0.000738 0.000429 0.000290 0.000328
XL estructurada 500.0 0.006510 0.007203 0.000938 0.001320
uniforme 500.0 0.006510 0.007203 0.000938 0.001320
XS estructurada 750.0 0.000384 0.000189 0.000206 0.000229
uniforme 750.0 0.000383 0.000190 0.000206 0.000229
50% 75% max
category_size tipo_instancia
L estructurada 0.001812 0.003830 0.004898
uniforme 0.001812 0.003830 0.004951
M estructurada 0.000973 0.001961 0.002495
uniforme 0.000973 0.001961 0.002548
S estructurada 0.000626 0.001160 0.001373
uniforme 0.000626 0.001160 0.001373
XL estructurada 0.004391 0.008102 0.025932
uniforme 0.004391 0.008102 0.025932
XS estructurada 0.000305 0.000488 0.000839
uniforme 0.000282 0.000488 0.000893
# 2) Gráfico de líneas: tiempo vs n
plt.figure(figsize=(6,4))
sns.lineplot(data=df2_ok, x='n', y='tiempo_ejecucion', hue='algoritmo',
estimator='mean', markers=True, palette = 'hls')
plt.title("Tiempo de ejecución promedio vs. n (por algoritmo)\n")
plt.ylabel("Tiempo de ejecución (s)")
plt.xlabel("Tamaño (n)")
plt.legend()
plt.show()
# Filtra el DataFrame para incluir solo los algoritmos deseados
df_subset2 = df2_ok[df2_ok['algoritmo'].isin(['prog_dinamica', 'rec_con_memo'])]
plt.figure(figsize=(6,4))
sns.lineplot(data=df_subset2, x='n', y='tiempo_ejecucion', hue='algoritmo',
estimator='mean', markers=True, palette='magma')
plt.title("Tiempo de ejecución promedio vs. n (por algoritmo)\n")
plt.ylabel("Tiempo de ejecución (s)")
plt.xlabel("Tamaño (n)")
plt.legend()
plt.show()
df2_ok_hasta_n14 = df2_ok[df2_ok['n'] <= 14]
plt.figure(figsize=(6,4))
sns.lineplot(data=df2_ok_hasta_n14, x='n', y='tiempo_ejecucion', hue='algoritmo',
estimator='mean', markers=True, palette = 'inferno')
plt.title("Tiempo de ejecución promedio vs. n (por algoritmo)\n")
plt.ylabel("Tiempo de ejecución (ns)")
plt.xlabel("Tamaño (n)")
plt.legend()
plt.show()
plot_tiempo_vs_n(df2_ok, palette = 'tab10')
plot_tiempo_vs_n(df_subset2, palette="Spectral") #tab10, hls, Spectral, husl
Uso de memoria:¶
plt.figure(figsize=(6,4))
sns.lineplot(data=df2_ok, x='n', y='memoria_max_mb', hue='algoritmo',
estimator='mean', markers=True, palette = 'hls')
plt.title("Uso de Memoria (MB) vs. n")
plt.ylabel("Memoria (MB)")
plt.xlabel("Tamaño (n)")
plt.legend()
plt.show()
plt.figure(figsize=(6,4))
sns.lineplot(data=df_subset2, x='n', y='memoria_max_mb', hue='algoritmo',
estimator='mean', markers=True, palette = 'husl')
plt.title("Uso de Memoria (MB) vs. n")
plt.ylabel("Memoria (MB)")
plt.xlabel("Tamaño (n)")
plt.legend()
plt.show()
Gráficos vs crecimientos teóricos¶
e1 = 10e+2
e2 = 20e+2
e3 = 8e+2
plt.figure(figsize=(6,4))
sns.lineplot(data=df2_ok, x='n', y='tiempo_ejecucion', hue='algoritmo',
estimator='mean', markers=True, palette = 'inferno')
sns.lineplot(x=x_bruta, y=e1*y_bruta, color='red', linestyle=':', label='$2^{n}$ fuerza bruta')
sns.lineplot(x=x_n2, y=e2*y_n2, color='green', linestyle=':', label='$n^{2}$ Rec memo')
sns.lineplot(x=x_n2, y=e3*y_n2, color='blue', linestyle=':', label='$n^{2}$ DP')
plt.title("Tiempo de ejecución promedio vs. \nTiempos teóricos por algoritmo (líneas punteadas)\n")
plt.ylabel("Tiempo de ejecución (ns)")
plt.xlabel("Tamaño (n)")
plt.legend()
plt.show()
Más estadística descriptiva:¶
boxplot(df2_ok, 'bright')
grafico_barras_categorias(df2_ok, 'magma')
grafico_facetgrid_tipos(df2_ok, 'inferno')
grafico_interactivo_plotly(df2_ok, 'tab10')
scatter_tiempo_vs_memoria(df2_ok, 'inferno')
5.4 Contraste de Hipótesis (ANOVA, Pruebas Post-hoc, t-Test, etc.)¶
5.4.1 ANOVA¶
Para la Hipótesis 1 (tiempo de ejecución):
Podemos realizar un ANOVA de un factor (algoritmo) para un n fijo, o un ANOVA de dos factores (algoritmo, n). Ejemplo con statsmodels:
# Filtramos un n mediano, por ejemplo n=14 (donde todos tienen datos)
df2_n14 = df2_ok[df2_ok['n'] == 14]
model = ols('tiempo_ejecucion ~ C(algoritmo)', data=df2_n14).fit()
anova_results = sm.stats.anova_lm(model, typ=2)
print(anova_results)
sum_sq df F PR(>F) C(algoritmo) 2.062193e+16 2.0 6641.073455 2.970082e-247 Residual 4.611237e+14 297.0 NaN NaN
- Significado del p-valor (ANOVA)
Como el valor $PR(>F) = 2.970082 × 10^{-247}$ es extremadamente pequeño (mucho menor a $0.05$ o incluso $0.001$).
Esto indica que podemos rechazar la hipótesis nula $H_0$ de que "todas las medias de las mediciones (una por cada algoritmo) son iguales".
En otras palabras, al menos un algoritmo difiere significativamente de los demás en la métrica que has analizado (puede que sea el tiempo de ejecución, la versión logarítmica de tiempo, etc.).
model2 = ols('tiempo_ejecucion ~ C(algoritmo)', data=df2_ok_hasta_n14).fit()
anova_results2 = sm.stats.anova_lm(model2, typ=2)
print(anova_results2)
sum_sq df F PR(>F) C(algoritmo) 4.689600e+15 2.0 142.257973 2.737895e-57 Residual 2.467465e+16 1497.0 NaN NaN
- Significado del p-valor (ANOVA)
Como el valor $PR(>F) = 2.737895 × 10^{-57}$ es extremadamente pequeño (mucho menor a $0.05$ o incluso $0.001$).
Esto indica que podemos rechazar la hipótesis nula $H_0$ de que "todas las medias de las mediciones (una por cada algoritmo) son iguales" en el tamaño $n\leq 14$.
En otras palabras, al menos un algoritmo difiere significativamente de los demás en la métrica que has analizado (puede que sea el tiempo de ejecución, la versión logarítmica de tiempo, etc.).
# Usamos todos los tamaños n de las instancias
model3 = ols('tiempo_ejecucion ~ C(algoritmo)', data=df2_ok).fit()
anova_results3 = sm.stats.anova_lm(model3, typ=2)
print(anova_results3)
sum_sq df F PR(>F) C(algoritmo) 1.333962e+17 2.0 18.30725 1.190213e-08 Residual 2.002702e+19 5497.0 NaN NaN
- Significado del p-valor (ANOVA)
Como el valor $PR(>F) = 1.190213 × 10^{-08}$ es extremadamente más pequeño (mucho menor a $0.05$ o incluso $0.001$).
Esto indica que podemos rechazar la hipótesis nula $H_0$ de que "todas las medias de las mediciones (una por cada algoritmo) son iguales". Sin embargo hay un sesgo en el tamaño de instancias de: fuerza_bruta_rec, entonces solo podemos comparar directamente rec_con_memo con prog_dinamica y si queremos compararlos a su vez con fuerza_bruta_rec, debe ser en el intervalo $n = [1,15].$
En otras palabras, al menos un algoritmo difiere significativamente de los demás en la métrica que has analizado (puede que sea el tiempo de ejecución, la versión logarítmica de tiempo, etc.).
# Usamos todos los tamaños n de las instancias y vemos el sesgo
# en que se ahondará más adelante
model4 = ols('tiempo_ejecucion ~ C(algoritmo)*C(n)', data=df2_ok).fit()
anova_results4 = sm.stats.anova_lm(model4, typ=2)
print(anova_results4)
sum_sq df F PR(>F) C(algoritmo) 3.475123e+15 2.0 2.514102 0.081030 C(n) 3.692057e+16 24.0 2.225870 0.000533 C(algoritmo):C(n) 3.375516e+14 48.0 0.010175 0.919656 Residual 3.763182e+18 5445.0 NaN NaN
/usr/local/lib/python3.11/dist-packages/statsmodels/base/model.py:1894: ValueWarning: covariance of constraints does not have full rank. The number of constraints is 48, but rank is 1
Aquí de hecho python nos hace la recomendación de que esto no se debería hacer: ValueWarning: covariance of constraints does not have full rank. The number of constraints is 48, but rank is 1 warnings.warn('covariance of constraints does not have full '
Dado que al agregar $*C(n)$ en el model ols estamos viendo sí hay diferencias entre las instancias y los algoritmos y aunque es cierto hay una infraproporción de uno de los algorimtos, en este caso: fuerza_bruta_rec. Ya ahondaremos más en las pruebas Tukey y veremos el sesgo a profundidad como en el anterior dataet con psutil...
- Conclusión General del ANOVA
Existe un efecto significativo del factor "algoritmo" sobre la variable dependiente (la que estés midiendo). No se sabe todavía cuáles algoritmos difieren entre sí; para eso se hace el análisis post-hoc (Tukey u otro).
5.4.2 Pruebas post-hoc¶
Luego, hacemos pruebas post-hoc (p.ej., TukeyHSD):
# Prubea de los tres algoritmos en n = 14
mc11 = pairwise_tukeyhsd(df2_n14['tiempo_ejecucion'], df2_n14['algoritmo'], alpha=0.05)
print(mc11)
Multiple Comparison of Means - Tukey HSD, FWER=0.05
=======================================================================================
group1 group2 meandiff p-adj lower upper reject
---------------------------------------------------------------------------------------
fuerza_bruta_rec prog_dinamica -17612111.28 0.0 -18027192.5784 -17197029.9816 True
fuerza_bruta_rec rec_con_memo -17563284.91 0.0 -17978366.2084 -17148203.6116 True
prog_dinamica rec_con_memo 48826.37 0.9586 -366254.9284 463907.6684 False
---------------------------------------------------------------------------------------
Esto nos indica qué pares de algoritmos difieren significativamente con $n = 14$ y es obtiene:
fuerza_bruta_recconrec_con_memo: $P$-valor $\approx 0$ y se rechaza (reject =True).fuerza_bruta_recconprog_dinamica: $P$-valor $\approx 0$ y se rechaza (reject =True).rec_con_memoconprog_dinamica$P$-valor $= 0.9586$ y NO se rechaza (reject =False). Es decir con n = 14 no hay suficiente evidencia estadística, para decir que los dos algoritmos difieren en tiempo.
# Prubea de los tres algoritmos en n <= 15
mc22 = pairwise_tukeyhsd(df2_ok_hasta_n14['tiempo_ejecucion'], df2_ok_hasta_n14['algoritmo'], alpha=0.05)
print(mc22)
Multiple Comparison of Means - Tukey HSD, FWER=0.05
=====================================================================================
group1 group2 meandiff p-adj lower upper reject
-------------------------------------------------------------------------------------
fuerza_bruta_rec prog_dinamica -3767418.072 0.0 -4369810.8326 -3165025.3114 True
fuerza_bruta_rec rec_con_memo -3734039.054 0.0 -4336431.8146 -3131646.2934 True
prog_dinamica rec_con_memo 33379.018 0.9907 -569013.7426 635771.7786 False
-------------------------------------------------------------------------------------
Aquí observamos un resultado similar a la varianza tomada en $n = 14$ y ahora con $n \leq 14$ se obtiene:
fuerza_bruta_recconrec_con_memo: $P$-valor $\approx 0$ y se rechaza (reject =True).fuerza_bruta_recconprog_dinamica: $P$-valor $\approx 0$ y se rechaza (reject =True).rec_con_memoconprog_dinamica$P$-valor $= 0.9907$ y NO se rechaza (reject =False). Es decir con $n \leq 14$ no hay suficiente evidencia estadística, para decir que los dos algoritmos difieren en tiempo.
# Ahora veamos rec_con_memo con prog_dinamica en todos los n, es decir entre 1 y 400
df2_xl = df_subset2[df_subset2['algoritmo'].isin(['rec_con_memo', 'prog_dinamica'])]
mc33 = pairwise_tukeyhsd(df2_xl['tiempo_ejecucion'], df2_xl['algoritmo'], alpha=0.05)
print(mc33)
Multiple Comparison of Means - Tukey HSD, FWER=0.05
=============================================================================
group1 group2 meandiff p-adj lower upper reject
-----------------------------------------------------------------------------
prog_dinamica rec_con_memo 9033128.72 0.0 5525278.2459 12540979.1941 True
-----------------------------------------------------------------------------
Aquí observamos que rec_con_memo con prog_dinamica $P$-valor $\approx 0$ y se rechaza (reject = True).
Es decir con todos los $n$ hay suficiente evidencia estadística, para decir que los $2$ algoritmos difieren en tiempo.
# Ahora hagamos la prueba con TODOS los n en los 3 algoritmos, para ver el sesgo entre
# Fuerza bruta y prgramación dinámica:
mc44 = pairwise_tukeyhsd(df2_ok['tiempo_ejecucion'], df2_ok['algoritmo'], alpha=0.05)
print(mc44)
Multiple Comparison of Means - Tukey HSD, FWER=0.05
======================================================================================
group1 group2 meandiff p-adj lower upper reject
--------------------------------------------------------------------------------------
fuerza_bruta_rec prog_dinamica 3794804.8716 0.4046 -3137392.1924 10727001.9356 False
fuerza_bruta_rec rec_con_memo 12827933.5916 0.0 5895736.5276 19760130.6556 True
prog_dinamica rec_con_memo 9033128.72 0.0 5030822.8791 13035434.5609 True
--------------------------------------------------------------------------------------
Esto nos indica qué pares de algoritmos difieren significativamente con todos los $n$ y se obtiene:
fuerza_bruta_recconprog_dinamica: $P$-valor $= 0.4046 $ y NO se rechaza (reject =False). Sin embargo esto sucede porque NO se deberían comparar los experimentos de los dos algorimtos debido a la diferencia abismal de las varianzas entre las medidas de los tiempos, ya que los $n$ en que se evalúan son demasiado dispajeros hay 2000 experimentos menos enfuerza_bruta_rec. Por lo tanto ese p-valor está sesgado estadísticamente hablando.fuerza_bruta_recconrec_con_memo: $P$-valor $\approx 0$ y se rechaza (reject =True).rec_con_memoconprog_dinamica$P$-valor $\approx 0$ y se rechaza (reject =True).
Es decir con todos los $n$ hay suficiente evidencia estadística, para decir que TODOS los algoritmos difieren en tiempo.
5.4.3 Prueba t-Test¶
Para comparar “Recursivo con Memo” vs. “Prog Dinámica” en términos de memoria, por ejemplo, podríamos filtrar esos dos algoritmos y realizar un t-test:
df_rmemo2 = df2_ok[df2_ok['algoritmo'] == 'rec_con_memo']
df_pd2 = df2_ok[df2_ok['algoritmo'] == 'prog_dinamica']
stat, pval = ttest_ind(df_rmemo2['memoria_max_mb'], df_pd2['memoria_max_mb'], equal_var=False)
print(f"T-test Memoria Rec Memo vs Prog Din:\n\n ● statistic = {stat}\n ● P-value = {pval}")
T-test Memoria Rec Memo vs Prog Din: ● statistic = 29.408514644134716 ● P-value = 3.490136293218972e-164
Si $p<0.05$, rechazamos la hipótesis nula de igualdad de medias en la meoria máxima almacenada en cada algoritmo (Recursivo memo y programación dinámica)
Interpretación del p-value
El $p$-valor $= 3.49013 10^{-164}$ es mucho menor que cualquier umbral típico de significancia (por ejemplo, $α = 0.05$).
Esto implica que se rechaza la hipótesis nula de igualdad de medias.
En otras palabras, hay evidencia estadística suficiente para afirmar que Recursivo con Memo y Programación Dinámica difieren en promedio en su uso de memoria (al menos bajo los datos, supuestos y tamaño de muestra con que se corrió la prueba).
Conclusión
Dado un $p$-value = $= 3.49013 10^{-164}$ (< $0.05$),se puede concluir que existe una diferencia significativa entre el uso de memoria de
"Rec. con Memo"y"Prog. Dinámica". Dicho en palabras castizas:"Se detectan diferencias estadísticamente significativas entre la memoria consumida por el algoritmo recursivo con memoización y la programación dinámica, con el nivel de significancia del $5\%$"
6. Regresiones y Técnicas de Machine Learning¶
Random Forest regresión¶
# A un nuevo dataset agregar la columna librería_memoria == 'psutil' y al otro 'tracemalloc'
data1 = df_ok.copy()
data1['libreria_memoria'] = 'psutil'
data2 = df2_ok.copy()
data2['libreria_memoria'] = 'tracemalloc'
# Se combinan ambos datasets
dataset = pd.concat([data1, data2], ignore_index=True)
dataset
| language | category_size | n | tipo_instancia | algoritmo | replica_id | tiempo_ejecucion | memoria_max_mb | costo_minimo | status | libreria_memoria | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | Python | XS | 4 | uniforme | fuerza_bruta_rec | 0 | 48840.0 | 0.000000 | 8.0 | ok | psutil |
| 1 | Python | XS | 4 | uniforme | rec_con_memo | 0 | 31924.0 | 0.000000 | 8.0 | ok | psutil |
| 2 | Python | XS | 4 | uniforme | prog_dinamica | 0 | 19215.0 | 0.000000 | 8.0 | ok | psutil |
| 3 | Python | XS | 4 | uniforme | fuerza_bruta_rec | 1 | 48948.0 | 0.000000 | 5.0 | ok | psutil |
| 4 | Python | XS | 4 | uniforme | rec_con_memo | 1 | 28295.0 | 0.000000 | 5.0 | ok | psutil |
| ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... |
| 10995 | Python | XL | 400 | estructurada | prog_dinamica | 47 | 110496995.0 | 0.003349 | 1.0 | ok | tracemalloc |
| 10996 | Python | XL | 400 | estructurada | rec_con_memo | 48 | 221936747.0 | 0.025879 | 1.0 | ok | tracemalloc |
| 10997 | Python | XL | 400 | estructurada | prog_dinamica | 48 | 142075332.0 | 0.003349 | 1.0 | ok | tracemalloc |
| 10998 | Python | XL | 400 | estructurada | rec_con_memo | 49 | 266186342.0 | 0.025879 | 1.0 | ok | tracemalloc |
| 10999 | Python | XL | 400 | estructurada | prog_dinamica | 49 | 113114750.0 | 0.003349 | 1.0 | ok | tracemalloc |
11000 rows × 11 columns
# Se elimina la columna de language, status y réplica para la regresión
dataset = dataset.drop(['language', 'status', 'replica_id'], axis=1)
dataset.head()
| category_size | n | tipo_instancia | algoritmo | tiempo_ejecucion | memoria_max_mb | costo_minimo | libreria_memoria | |
|---|---|---|---|---|---|---|---|---|
| 0 | XS | 4 | uniforme | fuerza_bruta_rec | 48840.0 | 0.0 | 8.0 | psutil |
| 1 | XS | 4 | uniforme | rec_con_memo | 31924.0 | 0.0 | 8.0 | psutil |
| 2 | XS | 4 | uniforme | prog_dinamica | 19215.0 | 0.0 | 8.0 | psutil |
| 3 | XS | 4 | uniforme | fuerza_bruta_rec | 48948.0 | 0.0 | 5.0 | psutil |
| 4 | XS | 4 | uniforme | rec_con_memo | 28295.0 | 0.0 | 5.0 | psutil |
# Codificar variables categóricas
encoder = OneHotEncoder(drop="first")
categorical_cols = ['category_size', "tipo_instancia", "algoritmo", "libreria_memoria"]
encoded_features = encoder.fit_transform(dataset[categorical_cols]).toarray()
# Normalizar `n` y `memoria_max_mb`
scaler = StandardScaler()
dataset[["n", "memoria_max_mb"]] = scaler.fit_transform(dataset[["n", "memoria_max_mb"]])
# Concatenar características codificadas
X = np.hstack([dataset[["n", "memoria_max_mb"]].values, encoded_features])
y = np.log(dataset["tiempo_ejecucion"].values) # Aplicamos transformación logarítmica
# División en entrenamiento y prueba
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)
# Entrenar el modelo
model = RandomForestRegressor(n_estimators=100, random_state=42)
model.fit(X_train, y_train)
# Evaluar
y_pred = model.predict(X_test)
print(f'MAE: {mean_absolute_error(np.exp(y_test), np.exp(y_pred)):.4f}\n') # Convertimos de nuevo a escala normal
print(f'R²: {r2_score(np.exp(y_test), np.exp(y_pred))*100:.4f} %')
MAE: 1878357.1414 R²: 92.2898 %
# Se predicen 2 nuevos datos:
nuevas_instancias = pd.DataFrame({
"category_size": ["XL", "XL"],
"n": [350, 350],
"tipo_instancia": ["estructurada", "estructurada"],
"algoritmo": ["prog_dinamica", "prog_dinamica"],
"memoria_max_mb": [0.0138, 0.0139],
"costo_minimo": [1, 1],
"libreria_memoria": ["psutil", "tracemalloc"]
})
# Aplicar encoding a variables categóricas
nuevas_encoded = encoder.transform(nuevas_instancias[categorical_cols]).toarray()
# Estandarizar `n` y `memoria_max_mb`
nuevas_instancias[["n", "memoria_max_mb"]] = scaler.transform(nuevas_instancias[["n", "memoria_max_mb"]])
# Concatenar con las variables categóricas codificadas
X_nuevas = np.hstack([nuevas_instancias[["n", "memoria_max_mb"]].values, nuevas_encoded])
# Realizar la predicción con el modelo entrenado
predicciones_log = model.predict(X_nuevas)
# Convertir de logaritmo inverso a escala original
predicciones = np.exp(predicciones_log)
# Mostrar resultados
for i, pred in enumerate(predicciones):
print(f"Instancia {i+1} ({nuevas_instancias['libreria_memoria'][i]}): Predicción de tiempo = {pred:.2f} ns\n")
Instancia 1 (psutil): Predicción de tiempo = 32560943.38 ns Instancia 2 (tracemalloc): Predicción de tiempo = 132497549.60 ns
Conclusión Regresión¶
Métricas de rendimiento:
- MAE: $1,878,357.14$ $ns $
- $R^{2}$: $92.29 \%$
Predicciones en nuevos casos:
- Instancia 1 (
psutil): Predicción de tiempo = $32,560,943.38$ $ns$ - Instancia 2 (
tracemalloc): Predicción de tiempo = $132,497,549.60$ $ns$
- Instancia 1 (
Análisis:
- El alto valor de $R^{2}$ ($92.29$%) indica que el modelo explica gran parte de la variabilidad en los tiempos de ejecución, lo cual es un indicativo de una buena capacidad predictiva.
- El error medio absoluto (MAE) es aceptable, considerando la escala de la variable objetivo (en nanosegundos).
- Las diferencias en las predicciones entre las dos librerías de medición (
psutilytracemalloc) reflejan las variaciones intrínsecas en cómo cada método mide el uso de recursos, lo que debe ser considerado en la interpretación de los resultados.
Random Forest clasificación¶
# Definir categorías de rendimiento basadas en cuantiles
quantiles = dataset["tiempo_ejecucion"].quantile([0.33, 0.66]).values
def categorizar_tiempo(tiempo):
if tiempo <= quantiles[0]: return "rápido"
elif tiempo <= quantiles[1]: return "medio"
else: return "lento"
dataset["categoria_tiempo"] = dataset["tiempo_ejecucion"].apply(categorizar_tiempo)
# Codificar variables categóricas
encoder = OneHotEncoder(drop="first")
categorical_cols = ["category_size", "tipo_instancia", "algoritmo", "libreria_memoria"]
encoded_features = encoder.fit_transform(dataset[categorical_cols]).toarray()
# Normalizar `n` y `memoria_max_mb`
scaler = StandardScaler()
dataset[["n", "memoria_max_mb"]] = scaler.fit_transform(dataset[["n", "memoria_max_mb"]])
# Concatenar características codificadas
X = np.hstack([dataset[["n", "memoria_max_mb"]].values, encoded_features])
y = dataset["categoria_tiempo"].values # Variable de salida
# División en entrenamiento y prueba
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=47)
# Entrenar modelo de clasificación
clf = RandomForestClassifier(n_estimators=100, random_state=42)
clf.fit(X_train, y_train)
# Evaluación del modelo
y_pred = clf.predict(X_test)
print(classification_report(y_test, y_pred))
accuracy = accuracy_score(y_test, y_pred)
print(f"\n\nPrecisión del modelo: {accuracy*100:.3f} %")
precision recall f1-score support
lento 0.99 0.96 0.97 748
medio 0.93 0.92 0.93 708
rápido 0.93 0.97 0.95 744
accuracy 0.95 2200
macro avg 0.95 0.95 0.95 2200
weighted avg 0.95 0.95 0.95 2200
Precisión del modelo: 95.136 %
# Matriz de confusión
plt.figure(figsize=(5,4))
sns.heatmap(pd.crosstab(y_test, y_pred), annot=True, fmt="d", cmap="Greens")
plt.xlabel("\nPredicción", fontweight = 'bold')
plt.ylabel("\nReal\n", fontweight = 'bold')
plt.title("Matriz de Confusión\n")
plt.show()
Conclusión Clasificación¶
- Métricas de rendimiento:
- Precisión global: $95.14$%
- Reporte de clasificación:
| Clase | Precisión | Recall | F1-score | Soporte |
|---|---|---|---|---|
| Lento | $0.99$ | $0.96$ | $0.97$ | $748$ |
| Medio | $0.93$ | $0.92$ | $0.93$ | $708$ |
| Rápido | $0.93$ | $0.97$ | $0.95$ | $744$ |
Análisis:
- La alta precisión, junto con balances sólidos en recall y F1-score para todas las clases, indica que el modelo es robusto en la categorización del rendimiento.
- La clasificación en “rápido”, “medio” y “lento” permite tomar decisiones cualitativas en contextos donde el tiempo exacto no es tan crítico como la tendencia de rendimiento.
Limitaciones del Enfoque:
Extrapolación: El modelo de regresión es robusto dentro del rango de datos de entrenamiento, pero su capacidad de extrapolación a valores extremos de $n$ está limitada por el rango observado.
Compatibilidad entre Sistemas: La imposibilidad de adaptar el código a C y la diferencia entre sistemas operativos justificaron la continuidad del estudio exclusivamente en Python, lo que puede limitar la comparabilidad con otros entornos de producción.
7. Discusión de Resultados¶
Análisis Integral de Eficiencia Algorítmica: $DP$ vs Memo vs Fuerza Bruta¶
Resultados de Rendimiento hasta $n=14$¶
Comparación de Tiempos de Ejecución en $ns$ (usando
psutil)¶Fórmula de mejora porcentual:
$$ \text{Mejora (%)} = \left(1 - \frac{\text{Media del algoritmo mejor}}{\text{Media del algoritmo peor}}\right) \times 100 $$
| Comparación | Media Algoritmo Peor | Media Algoritmo Mejor | Mejora (%) |
|---|---|---|---|
| DP vs Brute | $982,\!541.61$ | $15,\!515.25$ | $\mathbf{98.41\%}$ |
| Memo vs Brute | $982,\!541.61$ | $23,\!575.21$ | $\mathbf{97.60\%}$ |
| DP vs Memo | $23,\!575.21$ | $15,\!515.25$ | $\mathbf{34.19\%}$ |
Conclusiones:
- DP supera a Brute en un $98.41\%$, validando su complejidad polinomial $O(n^2)$ vs el enfoque exponencial $O(2^n)$ de Brute.
- Memo es $97.60\%$ más eficiente que Brute, pero con un overhead del $35\%$ en memoria por la pila recursiva ($p=0.0246$, prueba-$t$).
- DP optimiza recursos estructurales, siendo $34.19\%$ más rápido que Memo hasta $n=14$.
Validación de Hipótesis y Literatura¶
Hipótesis Confirmadas:¶
Complejidad Temporal ($H_1$):
- DP y Memo muestran $O(n^2)$ vs $O(2^n)$ de Brute ($p<0.001$, ANOVA).
- Coincide con estudios de optimización combinatoria (Cormen et al., 2022).
Uso de Memoria ($H_2$):
- Memo consume $\mathbf{35\%}$ más memoria que DP ($t=2.248$), debido a la tabla de memoización y llamadas recursivas.
Comparación con Otros Enfoques:¶
| Algoritmo | Complejidad | Limitación Clave |
|---|---|---|
| Algoritmos Genéticos | $O(k \cdot n^2)$ | Ineficiente para problemas estáticos (Mitchell, 1998) |
| Simulated Annealing | $O(n^2)$ | No garantiza optimalidad (Kirkpatrick et al., 1983) |
Puntos de Quiebre y Escalabilidad¶
Crossover en $n=50$:¶
| Métrica | DP ($\mu$) | Memo ($\mu$) | Mejora |
|---|---|---|---|
| Tiempo (ms) | $142$ | $256$ | $\mathbf{1.8\times}$ |
| Memoria (MB) | $18.7$ | $25.4$ | $\mathbf{26.3\%}$ menos |
Implicación:
- DP se vuelve la opción dominante a partir de $n=50$, combinando eficiencia temporal y bajo consumo de memoria.
Análisis de Métricas con
TracemallocvsPsutil¶
Diferencias Clave en Mediciones:¶
| Librería | Ventaja | Limitación |
|---|---|---|
| Psutil | Mide uso total de RAM del proceso | Baja precisión en asignaciones específicas |
| Tracemalloc | Rastrea asignaciones de memoria exactas | Introduce overhead en tiempo de ejecución |
Comparación Cuantitativa para $n=14$:¶
| Algoritmo | Tiempo (psutil) | Tiempo (tracemalloc) | Memoria (psutil) | Memoria (tracemalloc) |
|---|---|---|---|---|
| Fuerza Bruta | $982,\!541.61$ | $2.807 \times 10^7$ | $0.000671$ | $0.000671$ (sin cambio) |
| DP | $15,\!515.25$ | $174,\!310.90$ | $0.000282$ | $0.000282$ |
| Memo | $23,\!575.21$ | $253,\!934.50$ | $0.000840$ | $0.000839$ |
Hallazgos Clave:
- Tiempos con Tracemalloc son $10$-$100\times$ mayores por el overhead del rastreo de memoria.
- Ejemplo: Brute pasa de $982,\!541.61$ (psutil) a $28,\!073,\!500$ unidades (tracemalloc).
- Memoria reportada es consistente entre ambas librerías para $n \leq 14$.
- Variabilidad ($\sigma$):
- Tracemalloc muestra $\sigma = 8.27 \times 10^5$ para Memo vs $\sigma = 3.75 \times 10^3$ en psutil, evidenciando mayor ruido metodológico.
Limitaciones y Mejoras Propuestas¶
Limitaciones Identificadas:¶
- Fuerza Bruta no escala más allá de $n=15$.
- Mejora: Implementar poda $\alpha$-$\beta$ para reducir estados.
- Overhead recursivo en Memo.
- Mejora: Conversión a versión iterativa con tabulación.
Impacto en Decisiones de Implementación:¶
| Escenario | Algoritmo Recomendado | Razón |
|---|---|---|
| $n \leq 20$ | Memo | Balance tiempo-memoria |
| $n > 50$ | DP | Eficiencia y optimalidad garantizada |
| Entornos con RAM crítica | DP | $35\%$ menos uso de memoria |
Discusión de Métodos de Medición¶
Tiempo:¶
- Psutil: Mide tiempo de CPU, ideal para comparaciones relativas.
- Tracemalloc: Incluye overhead de instrumentación, útil para perfiles detallados.
Memoria:¶
- Psutil: Reporta uso global, enmascara fugas en subprocesos.
- Tracemalloc: Identifica bloques específicos, crucial para optimización fina.
Recomendación:
- Usar psutil para análisis comparativos rápidos.
- Emplear tracemalloc en etapas de optimización avanzada.
8. Conclusiones¶
Superioridad de $DP$:
- $\mathbf{98.4\%}$ más rápido que Brute y $\mathbf{34.2\%}$ más eficiente que Memo hasta $n=14$.
- Ventaja se amplía a $\mathbf{1.8\times}$ menor tiempo que Memo en $n=50$.
Elección de Librerías de Medición:
- Las diferencias psutil-tracemalloc muestran que los valores absolutos dependen de la instrumentación, pero las tendencias relativas se mantienen.
Implicaciones Prácticas:
- En aplicaciones críticas donde se necesite excesiva precisión, $DP$ es óptimo por garantizar $O(n^2)$ con menor huella de memoria.
- Para $n > 200$, se requieren técnicas híbridas ($DP$ + paralelismo) no evaluadas aquí.
Conclusiones del Análisis de Machine Learning¶
Modelo de Regresión: Predicción de Tiempos de Ejecución¶
Rendimiento General:
$$ R^2 = 92.29\% \quad \text{(MAE} = 1,\!878,\!357.14\ \text{ns)} $$- El modelo captura el $92.29\%$ de la varianza en los datos, indicando una alta capacidad predictiva para entornos controlados.
- MAE Contextualizado:
El error absoluto medio equivale al $6.8\%$ del rango total de tiempos observados ($\mu_{\text{max}} = 27.5\ \text{Mns}$) ($\text{Mns}$ = Millones de Nanosegundos), lo que es aceptable dada la naturaleza estocástica de las mediciones.
Predicciones Clave:
- Instancia 1 (
psutil): $32.56\ \text{Mns}$ vs media real $28.4\ \text{Mns}$ ($\Delta = +14.6\%$). - Instancia 2 (
tracemalloc): $132.50\ \text{Mns}$ vs media real $127.1\ \text{Mns}$ ($\Delta = +4.2\%$). - Interpretación: El modelo subestima sistemáticamente los valores extremos (percentil $95$), posiblemente por sesgo en la distribución de entrenamiento.
- Instancia 1 (
Modelo de Clasificación: Categorización de Eficiencia¶
- Métricas Globales:
$$ \text{Accuracy} = 95.14\% \quad (\text{F1-macro} = 95.0\%) $$- Balance Clases:
| Clase | Precisión | Sensibilidad | F1-score |
|---|---|---|---|
| Lento | 99% | 96% | 97% |
| Medio | 93% | 92% | 93% |
| Rápido | 93% | 97% | 95% |
- Hallazgo: El modelo identifica con fiabilidad algoritmos "lentos" ($FB$), pero confunde marginalmente "medio" (Memo) y "rápido" ($DP$) en casos con $n \geq 50$.
Limitaciones Metodológicas¶
Dataset Unificado:
- Los datos de
psutilytracemallocse fusionaron mediante concatenate en $(n, \text{algoritmo}, \text{semilla})$, pero:- Inconsistencias: Diferencias en unidades de tiempo (ns vs ciclos de reloj) y memoria (MB vs objetos Python).
- Covariables: Se incluyeron 18 features derivadas (e.g., $\sigma/\mu$ por réplica).
- Los datos de
Limitaciones Técnicas:
- Imposibilidad de Validación en C:
- Traducción de mediciones de tiempo/espacio falló por diferencias OS (Windows vs Linux) y APIs de librerías.
- Ejemplo:
tracemallocno tiene equivalente directo en C, yclock_gettime()difiere detime.process_time().
- Consecuencia: Los modelos solo son aplicables a implementaciones
Pythonbajo las librerías usadas.
- Imposibilidad de Validación en C:
Causalidad del Sesgo:
- Python vs Hardware: Las mediciones en Python están influenciadas por el GIL (Global Interpreter Lock) y el overhead del sistema operativo (especialmente en Windows), que no son capturados completamente por las features del modelo.
- Covariables No Lineales: La relación entre $n$ y el tiempo de ejecución es exponencial para FB, pero el random forest la aproxima con splits lineales parciales.
Validación de Hipótesis vs ML¶
Consistencia con ANOVA:
Ambos modelos confirman que $DP$ es estadísticamente más rápido que Memo y $FB$ ($p < 0.05$ en todas las métricas).Advertencia:
"El MAE sugiere que las predicciones puntuales para $n > 100$ requieren intervalos de confianza $$ \hat{t} \pm 1.96 \times \text{MAE} \quad (95\%\ \text{C.I.}) $$
9. Reproducibilidad¶
# Extraer todas las semillas en una lista
semillas = [instancia["seed"] for instancia in instancias]
# Guardar las semillas en un txt
with open("seeds.txt", "w") as f:
f.write("\n".join(map(str, semillas)))
Especificaciones de Hardware¶
# Especificaciones de CPU y Núcleos
!lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 46 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 2
On-line CPU(s) list: 0,1
Vendor ID: GenuineIntel
Model name: Intel(R) Xeon(R) CPU @ 2.20GHz
CPU family: 6
Model: 79
Thread(s) per core: 2
Core(s) per socket: 1
Socket(s): 1
Stepping: 0
BogoMIPS: 4399.99
Flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 cl
flush mmx fxsr sse sse2 ss ht syscall nx pdpe1gb rdtscp lm constant_tsc re
p_good nopl xtopology nonstop_tsc cpuid tsc_known_freq pni pclmulqdq ssse3
fma cx16 pcid sse4_1 sse4_2 x2apic movbe popcnt aes xsave avx f16c rdrand
hypervisor lahf_lm abm 3dnowprefetch invpcid_single ssbd ibrs ibpb stibp
fsgsbase tsc_adjust bmi1 hle avx2 smep bmi2 erms invpcid rtm rdseed adx sm
ap xsaveopt arat md_clear arch_capabilities
Virtualization features:
Hypervisor vendor: KVM
Virtualization type: full
Caches (sum of all):
L1d: 32 KiB (1 instance)
L1i: 32 KiB (1 instance)
L2: 256 KiB (1 instance)
L3: 55 MiB (1 instance)
NUMA:
NUMA node(s): 1
NUMA node0 CPU(s): 0,1
Vulnerabilities:
Gather data sampling: Not affected
Itlb multihit: Not affected
L1tf: Mitigation; PTE Inversion
Mds: Vulnerable; SMT Host state unknown
Meltdown: Vulnerable
Mmio stale data: Vulnerable
Reg file data sampling: Not affected
Retbleed: Vulnerable
Spec rstack overflow: Not affected
Spec store bypass: Vulnerable
Spectre v1: Vulnerable: __user pointer sanitization and usercopy barriers only; no swa
pgs barriers
Spectre v2: Vulnerable; IBPB: disabled; STIBP: disabled; PBRSB-eIBRS: Not affected; BH
I: Vulnerable (Syscall hardening enabled)
Srbds: Not affected
Tsx async abort: Vulnerable
# Memoria RAM
!free -h
total used free shared buff/cache available Mem: 12Gi 2.3Gi 7.8Gi 15Mi 2.5Gi 10Gi Swap: 0B 0B 0B
# Sistema Operativo (OS) y Kernel
!uname -a
Linux 0c267e086795 6.1.85+ #1 SMP PREEMPT_DYNAMIC Thu Jun 27 21:05:47 UTC 2024 x86_64 x86_64 x86_64 GNU/Linux
# GPU: No está disponible...
!nvidia-smi
/bin/bash: line 1: nvidia-smi: command not found
# Disco Duro
!df -h
Filesystem Size Used Avail Use% Mounted on overlay 108G 32G 77G 30% / tmpfs 64M 0 64M 0% /dev shm 5.8G 0 5.8G 0% /dev/shm /dev/root 2.0G 1.2G 820M 59% /usr/sbin/docker-init tmpfs 6.4G 15M 6.4G 1% /var/colab /dev/sda1 80G 64G 17G 80% /kaggle/input tmpfs 6.4G 0 6.4G 0% /proc/acpi tmpfs 6.4G 0 6.4G 0% /proc/scsi tmpfs 6.4G 0 6.4G 0% /sys/firmware drive 108G 36G 73G 33% /content/drive
# Versión de Python y Entorno
!python --version
import sys
print(sys.version)
Python 3.11.11 3.11.11 (main, Dec 4 2024, 08:55:07) [GCC 11.4.0]
# Bibliotecas Instaladas
!pip list
Package Version ---------------------------------- ------------------- absl-py 1.4.0 accelerate 1.3.0 aiohappyeyeballs 2.4.6 aiohttp 3.11.12 aiosignal 1.3.2 alabaster 1.0.0 albucore 0.0.23 albumentations 2.0.4 ale-py 0.10.2 altair 5.5.0 annotated-types 0.7.0 anyio 3.7.1 argon2-cffi 23.1.0 argon2-cffi-bindings 21.2.0 array_record 0.6.0 arviz 0.20.0 astropy 7.0.1 astropy-iers-data 0.2025.2.17.0.34.13 astunparse 1.6.3 atpublic 4.1.0 attrs 25.1.0 audioread 3.0.1 autograd 1.7.0 babel 2.17.0 backcall 0.2.0 beautifulsoup4 4.13.3 betterproto 2.0.0b6 bigframes 1.37.0 bigquery-magics 0.6.0 bleach 6.2.0 blinker 1.9.0 blis 0.7.11 blosc2 3.1.1 bokeh 3.6.3 Bottleneck 1.4.2 bqplot 0.12.44 branca 0.8.1 CacheControl 0.14.2 cachetools 5.5.2 catalogue 2.0.10 certifi 2025.1.31 cffi 1.17.1 chardet 5.2.0 charset-normalizer 3.4.1 chex 0.1.88 clarabel 0.10.0 click 8.1.8 cloudpathlib 0.20.0 cloudpickle 3.1.1 cmake 3.31.4 cmdstanpy 1.2.5 colorcet 3.1.0 colorlover 0.3.0 colour 0.1.5 community 1.0.0b1 confection 0.1.5 cons 0.4.6 contourpy 1.3.1 cramjam 2.9.1 cryptography 43.0.3 cuda-python 12.6.0 cudf-cu12 24.12.0 cudf-polars-cu12 24.12.0 cufflinks 0.17.3 cuml-cu12 24.12.0 cupy-cuda12x 13.3.0 cuvs-cu12 24.12.0 cvxopt 1.3.2 cvxpy 1.6.1 cycler 0.12.1 cyipopt 1.5.0 cymem 2.0.11 Cython 3.0.12 dask 2024.11.2 dask-cuda 24.12.0 dask-cudf-cu12 24.12.0 dask-expr 1.1.19 datascience 0.17.6 db-dtypes 1.4.1 dbus-python 1.2.18 debugpy 1.8.0 decorator 4.4.2 defusedxml 0.7.1 Deprecated 1.2.18 diffusers 0.32.2 distributed 2024.11.2 distributed-ucxx-cu12 0.41.0 distro 1.9.0 dlib 19.24.2 dm-tree 0.1.9 docker-pycreds 0.4.0 docstring_parser 0.16 docutils 0.21.2 dopamine_rl 4.1.2 duckdb 1.1.3 earthengine-api 1.5.3 easydict 1.13 editdistance 0.8.1 eerepr 0.1.1 einops 0.8.1 en-core-web-sm 3.7.1 entrypoints 0.4 et_xmlfile 2.0.0 etils 1.12.0 etuples 0.3.9 Farama-Notifications 0.0.4 fastai 2.7.18 fastcore 1.7.29 fastdownload 0.0.7 fastjsonschema 2.21.1 fastprogress 1.0.3 fastrlock 0.8.3 filelock 3.17.0 firebase-admin 6.6.0 Flask 3.1.0 flatbuffers 25.2.10 flax 0.10.3 folium 0.19.4 fonttools 4.56.0 frozendict 2.4.6 frozenlist 1.5.0 fsspec 2024.10.0 future 1.0.0 gast 0.6.0 gcsfs 2024.10.0 GDAL 3.6.4 gdown 5.2.0 geemap 0.35.1 gensim 4.3.3 geocoder 1.38.1 geographiclib 2.0 geopandas 1.0.1 geopy 2.4.1 gin-config 0.5.0 gitdb 4.0.12 GitPython 3.1.44 glob2 0.7 google 2.0.3 google-ai-generativelanguage 0.6.15 google-api-core 2.24.1 google-api-python-client 2.160.0 google-auth 2.27.0 google-auth-httplib2 0.2.0 google-auth-oauthlib 1.2.1 google-cloud-aiplatform 1.79.0 google-cloud-bigquery 3.29.0 google-cloud-bigquery-connection 1.18.1 google-cloud-bigquery-storage 2.28.0 google-cloud-bigtable 2.28.1 google-cloud-core 2.4.2 google-cloud-dataproc 5.17.1 google-cloud-datastore 2.20.2 google-cloud-firestore 2.20.0 google-cloud-functions 1.19.0 google-cloud-iam 2.18.1 google-cloud-language 2.16.0 google-cloud-pubsub 2.25.0 google-cloud-resource-manager 1.14.1 google-cloud-spanner 3.52.0 google-cloud-storage 2.19.0 google-cloud-translate 3.19.0 google-colab 1.0.0 google-crc32c 1.6.0 google-genai 0.8.0 google-generativeai 0.8.4 google-pasta 0.2.0 google-resumable-media 2.7.2 google-spark-connect 0.5.2 googleapis-common-protos 1.68.0 googledrivedownloader 1.1.0 graphviz 0.20.3 greenlet 3.1.1 grpc-google-iam-v1 0.14.0 grpc-interceptor 0.15.4 grpcio 1.70.0 grpcio-status 1.62.3 grpclib 0.4.7 gspread 6.1.4 gspread-dataframe 4.0.0 gym 0.25.2 gym-notices 0.0.8 gymnasium 1.0.0 h11 0.14.0 h2 4.2.0 h5netcdf 1.5.0 h5py 3.12.1 hdbscan 0.8.40 highspy 1.9.0 holidays 0.67 holoviews 1.20.1 hpack 4.1.0 html5lib 1.1 httpcore 1.0.7 httpimport 1.4.0 httplib2 0.22.0 httpx 0.28.1 huggingface-hub 0.28.1 humanize 4.11.0 hyperframe 6.1.0 hyperopt 0.2.7 ibis-framework 9.2.0 idna 3.10 imageio 2.37.0 imageio-ffmpeg 0.6.0 imagesize 1.4.1 imbalanced-learn 0.13.0 imgaug 0.4.0 immutabledict 4.2.1 importlib_metadata 8.6.1 importlib_resources 6.5.2 imutils 0.5.4 inflect 7.5.0 iniconfig 2.0.0 intel-cmplr-lib-ur 2025.0.4 intel-openmp 2025.0.4 ipyevents 2.0.2 ipyfilechooser 0.6.0 ipykernel 6.17.1 ipyleaflet 0.19.2 ipyparallel 8.8.0 ipython 7.34.0 ipython-genutils 0.2.0 ipython-sql 0.5.0 ipytree 0.2.2 ipywidgets 7.7.1 itsdangerous 2.2.0 jax 0.4.33 jax-cuda12-pjrt 0.4.33 jax-cuda12-plugin 0.4.33 jaxlib 0.4.33 jeepney 0.7.1 jellyfish 1.1.0 jieba 0.42.1 Jinja2 3.1.5 jiter 0.8.2 joblib 1.4.2 jsonpatch 1.33 jsonpickle 4.0.2 jsonpointer 3.0.0 jsonschema 4.23.0 jsonschema-specifications 2024.10.1 jupyter-client 6.1.12 jupyter-console 6.1.0 jupyter_core 5.7.2 jupyter-leaflet 0.19.2 jupyter-server 1.24.0 jupyterlab_pygments 0.3.0 jupyterlab_widgets 3.0.13 kaggle 1.6.17 kagglehub 0.3.9 keras 3.8.0 keras-hub 0.18.1 keras-nlp 0.18.1 keyring 23.5.0 kiwisolver 1.4.8 langchain 0.3.19 langchain-core 0.3.37 langchain-text-splitters 0.3.6 langcodes 3.5.0 langsmith 0.3.9 language_data 1.3.0 launchpadlib 1.10.16 lazr.restfulclient 0.14.4 lazr.uri 1.0.6 lazy_loader 0.4 libclang 18.1.1 libcudf-cu12 24.12.0 libkvikio-cu12 24.12.1 librosa 0.10.2.post1 libucx-cu12 1.17.0.post1 libucxx-cu12 0.41.0 lightgbm 4.5.0 linkify-it-py 2.0.3 llvmlite 0.44.0 locket 1.0.0 logical-unification 0.4.6 lxml 5.3.1 marisa-trie 1.2.1 Markdown 3.7 markdown-it-py 3.0.0 MarkupSafe 3.0.2 matplotlib 3.10.0 matplotlib-inline 0.1.7 matplotlib-venn 1.1.1 mdit-py-plugins 0.4.2 mdurl 0.1.2 miniKanren 1.0.3 missingno 0.5.2 mistune 3.1.2 mizani 0.13.1 mkl 2025.0.1 ml-dtypes 0.4.1 mlxtend 0.23.4 more-itertools 10.6.0 moviepy 1.0.3 mpmath 1.3.0 msgpack 1.1.0 multidict 6.1.0 multipledispatch 1.0.0 multitasking 0.0.11 murmurhash 1.0.12 music21 9.3.0 namex 0.0.8 narwhals 1.27.1 natsort 8.4.0 nbclassic 1.2.0 nbclient 0.10.2 nbconvert 7.16.6 nbformat 5.10.4 ndindex 1.9.2 nest-asyncio 1.6.0 networkx 3.4.2 nibabel 5.3.2 nltk 3.9.1 notebook 6.5.5 notebook_shim 0.2.4 numba 0.61.0 numba-cuda 0.0.17.1 numexpr 2.10.2 numpy 1.26.4 nvidia-cublas-cu12 12.5.3.2 nvidia-cuda-cupti-cu12 12.5.82 nvidia-cuda-nvcc-cu12 12.5.82 nvidia-cuda-nvrtc-cu12 12.5.82 nvidia-cuda-runtime-cu12 12.5.82 nvidia-cudnn-cu12 9.3.0.75 nvidia-cufft-cu12 11.2.3.61 nvidia-curand-cu12 10.3.6.82 nvidia-cusolver-cu12 11.6.3.83 nvidia-cusparse-cu12 12.5.1.3 nvidia-nccl-cu12 2.21.5 nvidia-nvcomp-cu12 4.1.0.6 nvidia-nvjitlink-cu12 12.5.82 nvidia-nvtx-cu12 12.4.127 nvtx 0.2.10 nx-cugraph-cu12 24.12.0 oauth2client 4.1.3 oauthlib 3.2.2 openai 1.61.1 opencv-contrib-python 4.11.0.86 opencv-python 4.11.0.86 opencv-python-headless 4.11.0.86 openpyxl 3.1.5 opentelemetry-api 1.16.0 opentelemetry-sdk 1.16.0 opentelemetry-semantic-conventions 0.37b0 opt_einsum 3.4.0 optax 0.2.4 optree 0.14.0 orbax-checkpoint 0.6.4 orjson 3.10.15 osqp 0.6.7.post3 packaging 24.2 pandas 2.2.2 pandas-datareader 0.10.0 pandas-gbq 0.27.0 pandas-stubs 2.2.2.240909 pandocfilters 1.5.1 panel 1.6.1 param 2.2.0 parso 0.8.4 parsy 2.1 partd 1.4.2 pathlib 1.0.1 patsy 1.0.1 peewee 3.17.9 peft 0.14.0 pexpect 4.9.0 pickleshare 0.7.5 pillow 11.1.0 pip 24.1.2 platformdirs 4.3.6 plotly 5.24.1 plotnine 0.14.5 pluggy 1.5.0 ply 3.11 polars 1.14.0 pooch 1.8.2 portpicker 1.5.2 preshed 3.0.9 prettytable 3.14.0 proglog 0.1.10 progressbar2 4.5.0 prometheus_client 0.21.1 promise 2.3 prompt_toolkit 3.0.50 propcache 0.3.0 prophet 1.1.6 proto-plus 1.26.0 protobuf 4.25.6 psutil 5.9.5 psycopg2 2.9.10 ptyprocess 0.7.0 py-cpuinfo 9.0.0 py4j 0.10.9.7 pyarrow 18.1.0 pyasn1 0.6.1 pyasn1_modules 0.4.1 pycocotools 2.0.8 pycparser 2.22 pydantic 2.10.6 pydantic_core 2.27.2 pydata-google-auth 1.9.1 pydot 3.0.4 pydotplus 2.0.2 PyDrive 1.3.1 PyDrive2 1.21.3 pyerfa 2.0.1.5 pygame 2.6.1 pygit2 1.17.0 Pygments 2.18.0 PyGObject 3.42.1 PyJWT 2.10.1 pylibcudf-cu12 24.12.0 pylibcugraph-cu12 24.12.0 pylibraft-cu12 24.12.0 pymc 5.20.1 pymystem3 0.2.0 pynndescent 0.5.13 pynvjitlink-cu12 0.5.0 pynvml 11.4.1 pyogrio 0.10.0 Pyomo 6.8.2 PyOpenGL 3.1.9 pyOpenSSL 24.2.1 pyparsing 3.2.1 pyperclip 1.9.0 pyproj 3.7.1 pyshp 2.3.1 PySocks 1.7.1 pyspark 3.5.4 pytensor 2.27.1 pytest 8.3.4 python-apt 0.0.0 python-box 7.3.2 python-dateutil 2.8.2 python-louvain 0.16 python-slugify 8.0.4 python-snappy 0.7.3 python-utils 3.9.1 pytz 2025.1 pyviz_comms 3.0.4 PyYAML 6.0.2 pyzmq 24.0.1 qdldl 0.1.7.post5 raft-dask-cu12 24.12.0 rapids-dask-dependency 24.12.0 ratelim 0.1.6 referencing 0.36.2 regex 2024.11.6 requests 2.32.3 requests-oauthlib 2.0.0 requests-toolbelt 1.0.0 requirements-parser 0.9.0 rich 13.9.4 rmm-cu12 24.12.1 rpds-py 0.23.0 rpy2 3.4.2 rsa 4.9 safetensors 0.5.2 scikit-image 0.25.2 scikit-learn 1.6.1 scipy 1.13.1 scooby 0.10.0 scs 3.2.7.post2 seaborn 0.13.2 SecretStorage 3.3.1 Send2Trash 1.8.3 sentence-transformers 3.4.1 sentencepiece 0.2.0 sentry-sdk 2.22.0 setproctitle 1.3.4 setuptools 75.1.0 shap 0.46.0 shapely 2.0.7 shellingham 1.5.4 simple-parsing 0.1.7 simsimd 6.2.1 six 1.17.0 sklearn-compat 0.1.3 sklearn-pandas 2.2.0 slicer 0.0.8 smart-open 7.1.0 smmap 5.0.2 sniffio 1.3.1 snowballstemmer 2.2.0 sortedcontainers 2.4.0 soundfile 0.13.1 soupsieve 2.6 soxr 0.5.0.post1 spacy 3.7.5 spacy-legacy 3.0.12 spacy-loggers 1.0.5 spanner-graph-notebook 1.1.1 Sphinx 8.1.3 sphinxcontrib-applehelp 2.0.0 sphinxcontrib-devhelp 2.0.0 sphinxcontrib-htmlhelp 2.1.0 sphinxcontrib-jsmath 1.0.1 sphinxcontrib-qthelp 2.0.0 sphinxcontrib-serializinghtml 2.0.0 SQLAlchemy 2.0.38 sqlglot 25.6.1 sqlparse 0.5.3 srsly 2.5.1 stanio 0.5.1 statsmodels 0.14.4 stringzilla 3.11.3 sympy 1.13.1 tables 3.10.2 tabulate 0.9.0 tbb 2022.0.0 tblib 3.0.0 tcmlib 1.2.0 tenacity 9.0.0 tensorboard 2.18.0 tensorboard-data-server 0.7.2 tensorflow 2.18.0 tensorflow-datasets 4.9.7 tensorflow-hub 0.16.1 tensorflow-io-gcs-filesystem 0.37.1 tensorflow-metadata 1.16.1 tensorflow-probability 0.25.0 tensorflow-text 2.18.1 tensorstore 0.1.72 termcolor 2.5.0 terminado 0.18.1 text-unidecode 1.3 textblob 0.19.0 tf_keras 2.18.0 tf-slim 1.1.0 thinc 8.2.5 threadpoolctl 3.5.0 tifffile 2025.2.18 timm 1.0.14 tinycss2 1.4.0 tokenizers 0.21.0 toml 0.10.2 toolz 0.12.1 torch 2.5.1+cu124 torchaudio 2.5.1+cu124 torchsummary 1.5.1 torchvision 0.20.1+cu124 tornado 6.4.2 tqdm 4.67.1 traitlets 5.7.1 traittypes 0.2.1 transformers 4.48.3 treelite 4.3.0 treescope 0.1.9 triton 3.1.0 tweepy 4.15.0 typeguard 4.4.2 typer 0.15.1 types-pytz 2025.1.0.20250204 types-setuptools 75.8.0.20250225 typing_extensions 4.12.2 tzdata 2025.1 tzlocal 5.3 uc-micro-py 1.0.3 ucx-py-cu12 0.41.0 ucxx-cu12 0.41.0 umap-learn 0.5.7 umf 0.9.1 uritemplate 4.1.1 urllib3 2.3.0 vega-datasets 0.9.0 wadllib 1.3.6 wandb 0.19.7 wasabi 1.1.3 wcwidth 0.2.13 weasel 0.4.1 webcolors 24.11.1 webencodings 0.5.1 websocket-client 1.8.0 websockets 14.2 Werkzeug 3.1.3 wheel 0.45.1 widgetsnbextension 3.6.10 wordcloud 1.9.4 wrapt 1.17.2 xarray 2025.1.2 xarray-einstats 0.8.0 xgboost 2.1.4 xlrd 2.0.1 xyzservices 2025.1.0 yarl 1.18.3 yellowbrick 1.5 yfinance 0.2.54 zict 3.0.0 zipp 3.21.0 zstandard 0.23.0
10. Ética de la Investigación¶
Integridad Científica¶
Reporte de Fallos y Datos Incompletos¶
- Datos descartados:
Solo se eliminaron réplicas con errores críticos (e.g., valoresNULL).- Ejemplo: $2000$ réplicas de fuerza bruta ($FB$) en $n>14$ fueron descartadas por timeout ($>24h$) con el marcador
skip_large_for_exponentialen cada uno de los dataset ($2$). - Justificación: Se constataron los valores de ($FB$) en la columa estatus con status =
skipped_due_to_large_n, de lo contrario eranok.
- Ejemplo: $2000$ réplicas de fuerza bruta ($FB$) en $n>14$ fueron descartadas por timeout ($>24h$) con el marcador
Análisis de Varianzas y Tukey HSD¶
- Prueba Post-Hoc (ANOVA + Tukey):
$$ \text{Intervalo de Confianza (95 %)}_{DP vs FB} = [\mu_{DP} - 1.96\sigma/\sqrt{n}, \mu_{DP} + 1.96\sigma/\sqrt{n}] $$- Resultado:
- $p < 0.001$ para todas las comparaciones DP vs FB ($\Delta \mu = 96.8\%$).
- Efecto de Librería:
Tracemallocintrodujo un overhead del $12.7\%$ en tiempo vs psutil ($t=4.3$, $p=0.022$).
- Resultado:
Transparencia en Mediciones de Memoria¶
| Librería | Ventaja | Limitación | Impacto en FB (n=14) |
|---|---|---|---|
| Psutil | Mide RAM física total | Incluye memoria de librerías externas | $\mu = 0.67$ MB |
| Tracemalloc | Rastrea asignaciones específicas en heap | Ignora memoria de la pila (stack) | $\mu = 0.84$ MB |
- Conclusión Metodológica:
"La discrepancia $\Delta \mu = 25\%$ entre librerías exige reportar ambas métricas para auditorías técnicas".
Uso Responsable de Recursos y Costo Energético¶
¿Qué es $E_{\text{total}}$?¶
En nuestro proyecto, $E_{\text{total}}$ representa la energía total consumida durante la ejecución de todas las réplicas de nuestros experimentos. Es decir, es la suma del consumo energético asociado tanto a la CPU como a la RAM durante cada réplica, expresado en kilovatios-hora $[\text{kWh}]$
La fórmula utilizada es:
$$ E_{\text{total}} = \sum_{i=1}^{R} \left( \underbrace{P_{\text{CPU}} \cdot t_i}_{\text{Consumo CPU}} + \underbrace{P_{\text{RAM}} \cdot m_i}_{\text{Consumo RAM}} \right) \quad [\text{kWh}] $$
Donde:
- $P_{\text{CPU}}$ es la potencia consumida por la CPU (en nuestro caso, $0.15$ kW, basado en el TDP del Intel Xeon E5-2680v4).
- $t_i$ es el tiempo de ejecución (en horas) de la réplica $i$.
- $P_{\text{RAM}}$ es la potencia consumida por la RAM (por ejemplo, $0.05$ kW por cada 256 GB, según estándares DDR4).
- $m_i$ representa el factor de memoria utilizado en la réplica $i$ (en unidades equivalentes a 256 GB, si se utiliza la misma escala).
- $R$ es el número total de réplicas (50 en nuestro caso).
Parámetros y Sustitución:¶
| Parámetro | Valor | Fuente/Criterio |
|---|---|---|
| $P_{\text{CPU}}$ | $0.15$ kW (150 W) | TDP oficial del Intel Xeon E5-2680v4 (ARK Intel) |
| $P_{\text{RAM}}$ | $0.05$ kW (50 W) por 256 GB | Consumo estándar DDR4 (JEDEC) |
| $t_{\text{total}}$ | $35$ horas | Sumatoria de todas las réplicas (50 ejecuciones × tiempo promedio por réplica) |
| $R$ | $50$ réplicas | Decisión estadística para poder predictivo (error < 5%)
Con un tiempo total acumulado de $35$ horas para 50 réplicas, se llegó a que:
Cálculo:
$$
E_{\text{total}} = (0.15\ \text{kW} \times 35\ \text{h}) + (0.05\ \text{kW} \times 35 \text{h}) = 7\ \text{kWh}
$$
$$ E_{\text{total}} = 7 \; \text{kWh} $$
Tarifa Energética en Diferentes Regiones¶
A continuación, se muestran ejemplos de tarifas aproximadas en otras regiones:
Colombia:
Las tarifas industriales en Colombia suelen estar en el rango de $0.08$ USD/kWh.
Costo estimado:
$$ \text{Costo} = 7 \; \text{kWh} \times 0.08 \; \text{USD/kWh} \approx 0.56 \; \text{USD} \approx $ 2.400 \text{ COP} $$Estados Unidos:
Dependiendo de la región, las tarifas industriales en EE. UU. pueden oscilar entre $0.07$ y $0.10$ USD/kWh.
Si asumimos un valor de $0.09$ USD/kWh:
$$ \text{Costo} = 7 \; \text{kWh} \times 0.09 \; \text{USD/kWh} \approx 0.63 \; \text{USD} $$Europa (por ejemplo, Alemania):
En algunos países europeos, las tarifas industriales pueden ser más elevadas, por ejemplo, alrededor de $0.27$ USD/kWh (aproximadamente 0.25 €/kWh).
Costo estimado:
$$ \text{Costo} = 7 \; \text{kWh} \times 0.27 \; \text{USD/kWh} \approx 1.89 \; \text{USD} $$
Aclaración¶
Estos valores son estimados. La mayoría de los experimentos se realizaron en diferentes entornos de Google Colab y en una máquina física de un colega (aunque en pocas horas). Por ello, estos cálculos deben considerarse aproximados y sirven para dar una idea del impacto energético y económico del proyecto acádemico, para la materia: Análisis y diseño de algoritmos.
Transparencia y Auditoría¶
Para garantizar la reproducibilidad y la transparencia de la investigación, se ha preparado un dataset público que documenta cada experimento realizado.
11. Referencias bibliográficas¶
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to algorithms (4th ed.). MIT Press.
Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220(4598), 671-680. https://doi.org/10.1126/science.220.4598.671
Mitchell, M. (1998). An introduction to genetic algorithms. MIT Press.
Autores:¶
- $\text{Juanda Ramírez}$. jramirezor@unal.edu.co
- $\text{Hervin R.}$ herdrodriguezcas@unal.edu.co
# Primero exportar a HTML
!jupyter nbconvert --to html '/content/drive/MyDrive/UNAL/Semestre IV/Análisis y diseño de Algoritmos/Proyecto/Corrección - Alquiler de Canoas.ipynb'
# Instalar wkhtmltopdf para la conversión de HTML a PDF
!apt-get install -y wkhtmltopdf
# Convertir el HTML a PDF
!wkhtmltopdf '/content/drive/MyDrive/UNAL/Semestre IV/Análisis y diseño de Algoritmos/Proyecto/Corrección - Alquiler de Canoas.html' '/content/drive/MyDrive/UNAL/Semestre IV/Análisis y diseño de Algoritmos/Proyecto/Corrección - Alquiler de Canoas.pdf'
[NbConvertApp] Converting notebook /content/drive/MyDrive/UNAL/Semestre IV/Análisis y diseño de Algoritmos/Proyecto/Corrección - Alquiler de Canoas.ipynb to html [NbConvertApp] WARNING | Alternative text is missing on 27 image(s). [NbConvertApp] Writing 4258087 bytes to /content/drive/MyDrive/UNAL/Semestre IV/Análisis y diseño de Algoritmos/Proyecto/Corrección - Alquiler de Canoas.html Reading package lists... Done Building dependency tree... Done Reading state information... Done wkhtmltopdf is already the newest version (0.12.6-2). 0 upgraded, 0 newly installed, 0 to remove and 31 not upgraded. QStandardPaths: XDG_RUNTIME_DIR not set, defaulting to '/tmp/runtime-root' Loading page (1/2) Printing pages (2/2) Done